Satisfiability certificates verifiable in subexponential time

DOI10.1007/978-3-642-21581-0_4MaRDI QIDQ3007671zbMATH OpenOpenAlexFDO

Authors E. Ya. Dantsin, Edward A. Hirsch

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)

Recommendations

• On the complexity of k-SAT
• Maximum satisfiability and subexponential time
• Parameterized and subexponential-time complexity of satisfiability problems and applications
• Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
• Time complexity of constraint satisfaction via universal algebra

Cites work

• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• A full derandomization of Schöning's \(k\)-\textsc{SAT} algorithm
• An algorithm for the satisfiability problem of formulas in conjunctive normal form
• An improved exponential-time algorithm for k -SAT
• scientific article; zbMATH DE number 1452705 (Why is no real title available?)
• Improving exhaustive search implies superpolynomial lower bounds
• On the complexity of k-SAT
• On the complexity of circuit satisfiability
• Which problems have strongly exponential complexity?

Cited in

(3)

• What's next? Future directions in parameterized complexity
• Verifiable certificates for predicate subtyping
• Does subset sum admit short proofs?

This page was built for publication: Satisfiability certificates verifiable in subexponential time

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