On the Exact Complexity of Evaluating Quantified k-CNF
From MaRDI portal
Publication:3058691
DOI10.1007/978-3-642-17493-3_7zbMath1309.68087OpenAlexW2176897270MaRDI QIDQ3058691
Chris Calabro, Russell Impagliazzo, Ramamohan Paturi
Publication date: 7 December 2010
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-17493-3_7
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Existentially restricted quantified constraint satisfaction
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Which problems have strongly exponential complexity?
- Resolution for quantified Boolean formulas
- The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
- An improved exponential-time algorithm for k -SAT
- The Complexity of Satisfiability of Small Depth Circuits
- An algorithm for the satisfiability problem of formulas in conjunctive normal form
- Theory and Applications of Satisfiability Testing
- On the complexity of \(k\)-SAT
This page was built for publication: On the Exact Complexity of Evaluating Quantified k-CNF
