On the exact complexity of evaluating quantified \(k\)-\textsc{cnf}
type: Item
instance of: scholarly article
title: On the exact complexity of evaluating quantified \(k\)-\textsc{cnf}
zbMATH Open document ID: 1262.68047
author: Chris Calabro
author: Russell Impagliazzo
author: Ramamohan Paturi
published in: Algorithmica
publication date: 2013-05-16T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 6163650
zbMATH Keywords: quantified Boolean formulas
zbMATH Keywords: satisfiability
MaRDI profile type: Publication
full work available at URL: s00453-012-9648-0
OpenAlex ID: W1973049078
cites work: A linear-time algorithm for testing the truth of certain quantified Boolean formulas
cites work: Resolution for quantified Boolean formulas
cites work: Existentially restricted quantified constraint satisfaction
cites work: The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
cites work: The Complexity of Satisfiability of Small Depth Circuits
cites work: Theory and Applications of Satisfiability Testing
cites work: 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
cites work: On the complexity of \(k\)-SAT
cites work: Which problems have strongly exponential complexity?
cites work: Improved Randomized Algorithms for 3-SAT
cites work: An improved exponential-time algorithm for k -SAT
cites work: Q4484662
cites work: Q3507036
cites work: A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
cites work: An algorithm for the satisfiability problem of formulas in conjunctive normal form
cites work: Q4828947
DOI: 10.1007/S00453-012-9648-0
description: scientific article; zbMATH DE number 6163650