Lower bounds for the polynomial calculus

We show that polynomial calculus proofs (sometimes also called Groebner proofs) of the pigeonhole principle \( P H P^m_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 \( P H P^m_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 \( \Omega(t/n) \). Loosely speaking, this means that low degree polynomial calculus proofs do not prove \( {\bf NP}\not\subseteq {\bf P}/poly \).

Authors and Affiliations

1. Department of Mathematical Logics, Steklov Mathematical Institute, Gubkina 8, 117966 Moscow GSP-1, Russia, e-mail: razborov@genesis.mi.ras.ru, , , , , , RU

   A.A. Razborov

Received: January 15, 1997.

Reprints and permissions