A new proof of the weak pigeonhole principle

DOI10.1145/335305.335348zbMath1296.03033OpenAlexW2095226356MaRDI QIDQ5895202

Alexis Maciel, Alan R. Woods, Toniann Pitassi

Publication date: 26 September 2014

Published in: Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/335305.335348

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Related Items (6)

On the complexity of resolution with bounded conjunctions ⋮ Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms ⋮ Propositional proof complexity ⋮ Structures interpretable in models of bounded arithmetic ⋮ A model-theoretic characterization of the weak pigeonhole principle ⋮ Lower bounds for the weak pigeonhole principle and random formulas beyond resolution

This page was built for publication: A new proof of the weak pigeonhole principle