On the exact complexity of evaluating quantified \(k\)-\textsc{cnf}

DOI10.1007/s00453-012-9648-0zbMath1262.68047OpenAlexW1973049078MaRDI QIDQ1949746

Chris Calabro, Russell Impagliazzo, Ramamohan Paturi

Publication date: 16 May 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9648-0

zbMATH Keywords

satisfiabilityquantified Boolean formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

The relative exponential time complexity of approximate counting satisfying assignments ⋮ The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments

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
• A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
• Which problems have strongly exponential complexity?
• Resolution for quantified Boolean formulas
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• Improved Randomized Algorithms for 3-SAT
• 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
• 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
• 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\)-\textsc{cnf}