Satisfiability Certificates Verifiable in Subexponential Time

DOI10.1007/978-3-642-21581-0_4zbMath1331.68101OpenAlexW1480076195MaRDI QIDQ3007671

Edward A. Hirsch, Evgeny Dantsin

Publication date: 17 June 2011

Published in: Theory and Applications of Satisfiability Testing - SAT 2011 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-21581-0_4

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (1)

What’s Next? Future Directions in Parameterized Complexity

Cites Work

• Unnamed Item
• Which problems have strongly exponential complexity?
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Improving exhaustive search implies superpolynomial lower bounds
• On the complexity of circuit satisfiability
• An improved exponential-time algorithm for k -SAT
• An algorithm for the satisfiability problem of formulas in conjunctive normal form
• A full derandomization of schöning's k-SAT algorithm
• On the complexity of \(k\)-SAT

This page was built for publication: Satisfiability Certificates Verifiable in Subexponential Time