Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms

DOI10.1016/S0304-3975(02)00394-8zbMath1017.03034MaRDI QIDQ1401230

Albert Atserias

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

bounded arithmetic; weak pigeonhole principle; bounded-depth Frege

Mathematics Subject Classification ID

03F30: First-order arithmetic and fragments

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03D10: Turing machines and related notions

03F20: Complexity of proofs

Related Items

The Complexity of Propositional Proofs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exponential lower bounds for the pigeonhole principle
• Resolution proofs of generalized pigeonhole principles
• The intractability of resolution
• Proof theory. 2nd ed
• Primes and their residue rings in models of open induction
• Combinatorial principles in elementary number theory
• The complexity of the pigeonhole principle
• Time-space tradeoffs for satisfiability
• Resolution lower bounds for perfect matching principles
• Resolution lower bounds for the weak pigeonhole principle
• Polynomial size proofs of the propositional pigeonhole principle
• The relative efficiency of propositional proof systems
• Provability of the pigeonhole principle and the existence of infinitely many primes
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• A new proof of the weak pigeonhole principle