Degree complexity for a modified pigeonhole principle

Archive for Mathematical Logic 42 (5):403-414 (2003)
  Copy   BIBTEX

Abstract

. We consider a modification of the pigeonhole principle, M P H P, introduced by Goerdt in [7]. 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 [9] and simplified by Impagliazzo, Pudlák and Sgall [8], 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 [7], 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 [6].

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,310

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Monotone Proofs of the Pigeon Hole Principle.R. Gavalda, A. Atserias & N. Galesi - 2001 - Mathematical Logic Quarterly 47 (4):461-474.
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.
Matrix Identities and the Pigeonhole Principle.Michael Soltys & Alasdair Urquhart - 2004 - Archive for Mathematical Logic 43 (3):351-357.
On the Indecomposability of $\omega^{N}$.Jared R. Corduan & François G. Dorais - 2012 - Notre Dame Journal of Formal Logic 53 (3):373-395.

Analytics

Added to PP
2013-11-23

Downloads
35 (#330,715)

6 months
1 (#415,900)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references