| Abstract | We show that polynomial calculus proofs (sometimes also called
Groebner proofs) of the pigeonhole principle PHP n must have degree
at least (n=2) 1 over any field. This is the first non-trivial lower
bound on the degree of polynomial calculus proofs obtained without
using unproved complexity assumptions. We also show that for some
modifications of PHP n , expressible by polynomials of at most
logarithmic degree, our bound can be improved to linear in the number
of variables. Finally, we show that for any Boolean function f n in n
variables, every polynomial calculus proof of the statement "f n
cannot be computed by any circuit of size t," must have degree
t=n). Loosely speaking, this means that low degree polynomial
calculus proofs do not prove NP 6 P=poly. |
