Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle and the Ordering Principle

preprint2022arXivOpen access

Abstract

In this paper, we investigate the total coefficient size of Nullstellensatz proofs. We show that Nullstellensatz proofs of the pigeonhole principle on nn pigeons require total coefficient size 2Ω(n)2^{Ω(n)} and that there exist Nullstellensatz proofs of the ordering principle on nn elements with total coefficient size 2n−n2^n - n.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.