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

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

Albert Atserias

Publication date: 17 August 2003

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00394-8

zbMATH Keywords

bounded arithmeticweak pigeonhole principlebounded-depth Frege

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10) Complexity of proofs (03F20)

Related Items (3)

Iterated multiplication in \(VTC^0\) ⋮ The Complexity of Propositional Proofs ⋮ Resolution and the binary encoding of combinatorial principles

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

This page was built for publication: Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms