A new proof of the weak pigeonhole principle
From MaRDI portal
Publication:5894824
DOI10.1006/jcss.2002.1830zbMath1051.03049MaRDI QIDQ5894824
Toniann Pitassi, Alexis Maciel, Alan R. Woods
Publication date: 12 September 2002
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.2002.1830
03F20: Complexity of proofs
Related Items
NP search problems in low fragments of bounded arithmetic, Approximate counting in bounded arithmetic, The Complexity of Propositional Proofs, A note on propositional proof complexity of some Ramsey-type statements, On the automatizability of resolution and related propositional proof systems, Dual weak pigeonhole principle, Boolean complexity, and derandomization, Circuit principles and weak pigeonhole variants, Upper and lower Ramsey bounds in bounded arithmetic, Separation results for the size of constant-depth propositional proofs, Approximate counting by hashing in bounded arithmetic, The polynomial and linear hierarchies in models where the weak pigeonhole principle fails, Abelian groups and quadratic residues in weak arithmetic
Cites Work
- Exponential lower bounds for the pigeonhole principle
- Resolution proofs of generalized pigeonhole principles
- Combinatorial principles in elementary number theory
- Polynomial size proofs of the propositional pigeonhole principle
- On models of arithmetic having non-modular substructure lattices
- Provability of the pigeonhole principle and the existence of infinitely many primes
- Lower bounds to the size of constant-depth propositional proofs
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- Regular resolution lower bounds for the weak pigeonhole principle
- Natural proofs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
