Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
We show that the minimum total coefficient size of a Nullstellensatz proof of the pigeonhole principle on n+1 pigeons and n holes is 2^{Θ(n)}. We also investigate the ordering principle and construct an explicit Nullstellensatz proof for the ordering principle on n elements with total coefficient size 2ⁿ - n.