Archive for Mathematical Logic 42 (5):403-414 (2003)
Abstract. We consider a modification of the pigeonhole principle, M P H P, introduced by Goerdt in . M P H P is defined over n pigeons and log n holes, and more than one pigeon can go into a hole. Using a technique of Razborov  and simplified by Impagliazzo, Pudlák and Sgall , we prove that any Polynomial Calculus refutation of a set of polynomials encoding the M P H P, requires degree Ω. We also prove a simple Lemma giving a simulation of Resolution by Polynomial Calculus. Using this lemma, and a Resolution upper bound by Goerdt , we obtain that the degree lower bound is tight. Our lower bound establishes the optimality of the tree-like Resolution simulation by the Polynomial Calculus given in .
Similar books and articles
An Induction Principle and Pigeonhole Principles for K-Finite Sets.Andreas Blass - 1995 - Journal of Symbolic Logic 60 (4):1186-1193.
Monotone Proofs of the Pigeon Hole Principle.R. Gavalda, A. Atserias & N. Galesi - 2001 - Mathematical Logic Quarterly 47 (4):461-474.
Polynomial Size Proofs of the Propositional Pigeonhole Principle.Samuel R. Buss - 1987 - Journal of Symbolic Logic 52 (4):916-927.
Isols and the Pigeonhole Principle.J. C. E. Dekker & E. Ellentuck - 1989 - Journal of Symbolic Logic 54 (3):833-846.
The Weak Pigeonhole Principle for Function Classes in S12.Norman Danner & Chris Pollett - 2006 - Mathematical Logic Quarterly 52 (6):575-584.
Dual Weak Pigeonhole Principle, Boolean Complexity, and Derandomization.Emil Jeřábek - 2004 - Annals of Pure and Applied Logic 129 (1-3):1-37.
On Tao's “Finitary” Infinite Pigeonhole Principle.Jaime Gaspar & Ulrich Kohlenbach - 2010 - Journal of Symbolic Logic 75 (1):355-371.
Geometric Cardinal Invariants, Maximal Functions and a Measure Theoretic Pigeonhole Principle.Juris Steprāns - 2005 - Bulletin of Symbolic Logic 11 (4):517-525.
Matrix Identities and the Pigeonhole Principle.Michael Soltys & Alasdair Urquhart - 2004 - Archive for Mathematical Logic 43 (3):351-357.
An Exponential Separation Between the Parity Principle and the Pigeonhole Principle.Paul Beame & Toniann Pitassi - 1996 - Annals of Pure and Applied Logic 80 (3):195-228.
Lower Bounds to the Size of Constant-Depth Propositional Proofs.Jan Krajíček - 1994 - Journal of Symbolic Logic 59 (1):73-86.
On the Degree of Complexity of Sentential Logics.II. An Example of the Logic with Semi-Negation.Jacek Hawranek & Jan Zygmunt - 1984 - Studia Logica 43 (4):405 - 413.
Added to PP
Historical graph of downloads