We report lower bounds on total coefficient size in Nullstellensatz proofs of the Pigeonhole and Ordering Principles, indicating significant complexity.
We study the total coefficient size of Nullstellensatz proofs. We show that any Nullstellensatz proof of the pigeonhole principle on n pigeons and $n - 1$ holes has total coefficient size at least 2Ω(n), and that there is a Nullstellensatz proof of the ordering principle on n elements with total coefficient size 2ⁿ - n.
No takes yet. Share an insight, caveat, or question.
Aaron Zhang (2022) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: