An exponential separation between regular and general resolution
From MaRDI portal
Publication:3579185
DOI10.1145/509907.509974zbMath1192.03039OpenAlexW2040813688MaRDI QIDQ3579185
Michael Alekhnovich, Toniann Pitassi, Alasdair Urquhart, Jan Johannsen
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.509974
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Related Items (7)
Towards NP-P via proof complexity and search ⋮ The depth of resolution proofs ⋮ The NP-hardness of finding a directed acyclic graph for regular resolution ⋮ An unexpected separation result in Linearly Bounded Arithmetic ⋮ Limitations of restricted branching in clause learning ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT ⋮ Large clique is hard on average for resolution
This page was built for publication: An exponential separation between regular and general resolution
