期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1997
卷号：1997
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Razborov~\cite{Razborov96} recently proved that polynomial
calculus proofs of the pigeonhole principle PHPnm must have
degree at least \ceilingn2+1 over any field. We present a
simplified proof of the same result. The main
idea of our proof is the same as in the original proof
of Razborov: we want to describe explicitly the vector space of
the polynomials derivable in a low degree polynomial calculus
refutation of the pigeonhole principle, and the description uses
the pigeon dance as before. We are able to avoid some of the
technical machinery, due to the simple counting argument which
shows that the set of polynomials, which generates the vector
space of consequences, forms its basis.
Furthermore we show a matching upper bound on the polynomial
calculus proofs of the pigeonhole principle for any field of
sufficiently large characteristic,
and an \ceilingn2+1 lower bound for any subset sum problem
over the field of reals.
