k-SAT Is No Harder Than Decision-Unique-k-SAT
From MaRDI portal
Publication:3392942
DOI10.1007/978-3-642-03351-3_8zbMath1248.68237OpenAlexW1573449427MaRDI QIDQ3392942
Chris Calabro, Ramamohan Paturi
Publication date: 18 August 2009
Published in: Computer Science - Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-03351-3_8
independent setquantified Boolean formulashitting setunique satisfiabilityexponential complexity\(k\)-SAT
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- NP is as easy as detecting unique solutions
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Which problems have strongly exponential complexity?
- The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
- SAT-Problems and Reductions with Respect to the Number of Variables
- On the complexity of \(k\)-SAT
This page was built for publication: k-SAT Is No Harder Than Decision-Unique-k-SAT
