The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
From MaRDI portal
Publication:2475410
DOI10.1016/j.jcss.2007.06.015zbMath1135.68020OpenAlexW2092928619WikidataQ56767456 ScholiaQ56767456MaRDI QIDQ2475410
Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi, Chris Calabro
Publication date: 11 March 2008
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2007.06.015
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
Separating OR, SUM, and XOR circuits, The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems, Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models, The relative exponential time complexity of approximate counting satisfying assignments, Completeness, approximability and exponential time results for counting problems with easy decision version, The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments, Some rainbow problems in graphs have complexity equivalent to satisfiability problems, The Time Complexity of Constraint Satisfaction, A randomized algorithm for 3-SAT, Parameterized random complexity, On the exact complexity of evaluating quantified \(k\)-\textsc{cnf}, Unique (optimal) solutions: complexity results for identifying and locating-dominating codes, The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs, On the Exact Complexity of Evaluating Quantified k-CNF, Unnamed Item, Approximation algorithms for replenishment problems with fixed turnover times, Variable Influences in Conjunctive Normal Forms, k-SAT Is No Harder Than Decision-Unique-k-SAT, Exploiting functional dependencies in declarative problem specifications, Derandomizing Isolation in Space-Bounded Settings, The Complexity of Satisfiability of Small Depth Circuits, On Super Strong ETH
Cites Work
- Unnamed Item
- Unnamed Item
- Solving satisfiability in less than \(2^ n\) steps
- NP is as easy as detecting unique solutions
- A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
- Which problems have strongly exponential complexity?
- Two systems for proving tautologies, based on the split method
- A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
- Parametrized complexity theory.
- Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms
- An improved exponential-time algorithm for k -SAT
- SAT-Problems and Reductions with Respect to the Number of Variables
- An algorithm for the satisfiability problem of formulas in conjunctive normal form
- A necessary condition on minimal cube numberings
