An improved exponential-time algorithm for k -SAT

DOI10.1145/1066100.1066101zbMath1297.68217OpenAlexW2049136377WikidataQ105952258 ScholiaQ105952258MaRDI QIDQ3546306

Francis Zane, Pavel Pudlák, Ramamohan Paturi, Michael E. Saks

Publication date: 21 December 2008

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1066100.1066101

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)

Related Items (56)

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ A comparative runtime analysis of heuristic algorithms for satisfiability problems ⋮ Local Reductions ⋮ What Circuit Classes Can Be Learned with Non-Trivial Savings? ⋮ The complexity of depth-3 circuits computing symmetric Boolean functions ⋮ Local reduction ⋮ Exploiting partial knowledge of satisfying assignments ⋮ Matrix rigidity of random Toeplitz matrices ⋮ A satisfiability algorithm and average-case hardness for formulas over the full binary basis ⋮ A Computing Procedure for Quantification Theory ⋮ Algorithms for four variants of the exact satisfiability problem ⋮ Strong ETH and resolution via games and the multiplicity of strategies ⋮ Unnamed Item ⋮ Further improvements for SAT in terms of formula length ⋮ Improving resolution width lower bounds for \(k\)-CNFs with applications to the strong exponential time hypothesis ⋮ Towards NP-P via proof complexity and search ⋮ Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms ⋮ A randomized algorithm for 3-SAT ⋮ Analysis of local search landscapes for \(k\)-SAT instances ⋮ Unnamed Item ⋮ Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. ⋮ Worst-case study of local search for MAX-\(k\)-SAT. ⋮ On the structure and the number of prime implicants of 2-\(\mathsf{CNF}\)s ⋮ On the complexity of unique circuit SAT ⋮ On the exact complexity of evaluating quantified \(k\)-\textsc{cnf} ⋮ An exact algorithm for the Boolean connectivity problem for \(k\)-CNF ⋮ Unnamed Item ⋮ Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT ⋮ Absorbing random walks and the NAE2SAT problem ⋮ Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT ⋮ Local search for Boolean satisfiability with configuration checking and subscore ⋮ Satisfiability Certificates Verifiable in Subexponential Time ⋮ Prediction from partial information and hindsight, an alternative proof ⋮ The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs ⋮ Computing branchwidth via efficient triangulations and blocks ⋮ Unnamed Item ⋮ UnitWalk: A new SAT solver that uses local search guided by unit clause elimination ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Exact Complexity of Evaluating Quantified k-CNF ⋮ An improvement of the algorithm of Hertli for the unique 3SAT problem ⋮ A note on the fine-grained complexity of MIS on regular graphs ⋮ On extremal \(k\)-CNF formulas ⋮ Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences ⋮ Super strong ETH is true for PPSZ with small resolution width ⋮ The Boolean satisfiability problem in Clifford algebra ⋮ The Complexity of Satisfiability of Small Depth Circuits ⋮ On Super Strong ETH ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ On converting CNF to DNF ⋮ A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search. ⋮ Unnamed Item ⋮ A new algorithm for optimal 2-constraint satisfaction and its implications ⋮ Which problems have strongly exponential complexity? ⋮ Walksat Stalls Well Below Satisfiability ⋮ A \#SAT algorithm for small constant-depth circuits with PTF gates

This page was built for publication: An improved exponential-time algorithm for k -SAT