An improved exponential-time algorithm for k -SAT

DOI10.1145/1066100.1066101zbMATH Open1297.68217OpenAlexW2049136377WikidataQ105952258 ScholiaQ105952258MaRDI QIDQ3546306FDOQ3546306

Authors: Ramamohan Paturi, Pavel Pudlák, Francis Zane, Michael Saks Edit this on Wikidata

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

Recommendations

• scientific article; zbMATH DE number 1670827
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Publication:4484662
• A Better Algorithm for Random k-SAT
• A probabilistic algorithm for \(k\)-SAT based on limited local search and restart

Mathematics Subject Classification ID

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

Cited In (71)

• The complexity of depth-3 circuits computing symmetric Boolean functions
• Absorbing random walks and the NAE2SAT problem
• Towards NP-P via proof complexity and search
• Tighter connections between Formula-SAT and shaving logs
• Chain, generalization of covering code, and deterministic algorithm for \(k\)-SAT
• A comparative runtime analysis of heuristic algorithms for satisfiability problems
• Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences
• A \#SAT algorithm for small constant-depth circuits with PTF gates
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Worst-case study of local search for MAX-\(k\)-SAT.
• Strong ETH and resolution via games and the multiplicity of strategies
• A Computing Procedure for Quantification Theory
• Title not available (Why is that?)
• Theory and Applications of Satisfiability Testing
• Which problems have strongly exponential complexity?
• Walksat Stalls Well Below Satisfiability
• Computing branchwidth via efficient triangulations and blocks
• Local reduction
• Algorithms for four variants of the exact satisfiability problem
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• A note on the fine-grained complexity of MIS on regular graphs
• Exploiting partial knowledge of satisfying assignments
• On the possibility of faster \textsc{SAT} algorithms
• The complexity of satisfiability of small depth circuits
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
• Title not available (Why is that?)
• Improving resolution width lower bounds for \(k\)-CNFs with applications to the strong exponential time hypothesis
• The Boolean satisfiability problem in Clifford algebra
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• On converting CNF to DNF
• Analysis of local search landscapes for \(k\)-SAT instances
• On the structure and the number of prime implicants of 2-\(\mathsf{CNF}\)s
• Local search for Boolean satisfiability with configuration checking and subscore
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• A new algorithm for optimal 2-constraint satisfaction and its implications
• On the complexity of circuit satisfiability
• On extremal \(k\)-CNF formulas
• On super strong ETH
• A satisfiability algorithm for \(\mathrm{AC}^0\)
• On the exact complexity of evaluating quantified \(k\)-\textsc{cnf}
• Theory and Applications of Satisfiability Testing
• On the exact complexity of evaluating quantified \(k\)-CNF
• An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
• Exponential lower bounds for the PPSZ \(k\)-SAT algorithm
• Prediction from partial information and hindsight, an alternative proof
• UnitWalk: A new SAT solver that uses local search guided by unit clause elimination
• Matrix rigidity of random Toeplitz matrices
• Title not available (Why is that?)
• Satisfiability certificates verifiable in subexponential time
• Algorithms – ESA 2005
• On extremal \(k\)-CNF formulas
• Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT
• A randomized algorithm for 3-SAT
• On the complexity of unique circuit SAT
• Local reductions
• An approximation algorithm for \(\#k\)-SAT
• Further improvements for SAT in terms of formula length
• Super strong ETH is true for PPSZ with small resolution width
• Title not available (Why is that?)
• On conflict-free cuts: algorithms and complexity
• Title not available (Why is that?)
• A \#SAT algorithm for small constant-depth circuits with PTF gates
• Depth-3 circuits for inner product
• On super strong ETH
• An improvement of the algorithm of Hertli for the unique 3SAT problem
• PPSZ for general \(k\)-SAT and CSP -- making Hertli's analysis simpler and 3-SAT faster
• CNF satisfiability in a subspace and related problems
• Mind the gap: achieving a super-Grover quantum speedup by jumping to the end
• What circuit classes can be learned with non-trivial savings?

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3546306)