Files

Abstract

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^{\Omega(n)}$, and that there is a Nullstellensatz proof of the ordering principle on $n$ elements with total coefficient size $2^n - n$.

Details

Actions

PDF

from
to
Export
Download Full History