Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleLower Bounds for the Polynomial Calculus
Author(s) Alexander A. Razborov
TypeArticle in Journal
AbstractWe 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.
JournalElectronic Colloquium on Computational Complexity (ECCC)
Translation No
Refereed No