Resolution lower bounds for the weak pigeonhole principle
From MaRDI portal
Publication:3579188
DOI10.1145/509907.509987zbMath1192.03043OpenAlexW2143313747MaRDI QIDQ3579188
Publication date: 5 August 2010
Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/509907.509987
Related Items (8)
Resolution lower bounds for perfect matching principles ⋮ Mutilated chessboard problem is exponentially hard for resolution ⋮ On the complexity of resolution with bounded conjunctions ⋮ Towards NP-P via proof complexity and search ⋮ Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms ⋮ Exploiting subproblem optimization in SAT-based maxsat algorithms ⋮ Resolution for Max-SAT ⋮ Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
This page was built for publication: Resolution lower bounds for the weak pigeonhole principle
