An exponential separation between regular and general resolution

DOI10.1145/509907.509974MaRDI QIDQ3579185zbMATH OpenOpenAlexFDO

Authors Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart

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

Mathematics Subject Classification ID

Complexity of proofs (03F20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited in

(7)

• Large clique is hard on average for resolution
• Limitations of restricted branching in clause learning
• Towards NP-P via proof complexity and search
• An unexpected separation result in Linearly Bounded Arithmetic
• The depth of resolution proofs
• Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
• The NP-hardness of finding a directed acyclic graph for regular resolution

This page was built for publication: An exponential separation between regular and general resolution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3579185)