Resolution lower bounds for the weak pigeonhole principle
From MaRDI portal
Publication:3579188
DOI10.1145/509907.509987zbMath1192.03043MaRDI 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
03F20: Complexity of proofs
Related Items
Towards NP-P via proof complexity and search, Exploiting subproblem optimization in SAT-based maxsat algorithms, Resolution for Max-SAT, Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms, Lower bounds for the weak pigeonhole principle and random formulas beyond resolution, Resolution lower bounds for perfect matching principles, Mutilated chessboard problem is exponentially hard for resolution, On the complexity of resolution with bounded conjunctions