Satisfiability Certificates Verifiable in Subexponential Time
From MaRDI portal
Publication:3007671
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
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (1)
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
