A deterministic (2-2/(k+1))^n algorithm for k-SAT based on local search.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

scientific article; zbMATH DE number 1834642
scientific article; zbMATH DE number 1670827
A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
scientific article; zbMATH DE number 1241386
An improved deterministic local search algorithm for 3-SAT
Local search algorithms for SAT: an empirical evaluation
Local search algorithms for SAT: an empirical evaluation
Local maxima and improved exact algorithm for MAX-2-SAT
An approximation algorithm for \(\#k\)-SAT

Cites work

scientific article; zbMATH DE number 54154 (Why is no real title available?)
scientific article; zbMATH DE number 1024657 (Why is no real title available?)
scientific article; zbMATH DE number 1113996 (Why is no real title available?)
scientific article; zbMATH DE number 1452705 (Why is no real title available?)
scientific article; zbMATH DE number 1555929 (Why is no real title available?)
scientific article; zbMATH DE number 3228255 (Why is no real title available?)
An improved exponential-time algorithm for k -SAT
Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems
New methods for 3-SAT decision and worst-case analysis
New worst-case upper bounds for SAT
Number of models and satisfiability of sets of clauses
On the greedy algorithm for satisfiability
SAT local search algorithms: Worst-case study
Solving satisfiability in less than \(2^ n\) steps

Cited in

(53)

Modelling the dynamics of stochastic local search on \(k\)-SAT
Worst-case study of local search for MAX-\(k\)-SAT.
Unrestricted vs restricted cut in a tableau method for Boolean circuits
Sequential vector packing
scientific article; zbMATH DE number 1834642 (Why is no real title available?)
The complexity of Boolean constraint satisfaction local search problems
Improving exact algorithms for MAX-2-SAT
Computing branchwidth via efficient triangulations and blocks
The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
Guided Search and a Faster Deterministic Algorithm for 3-SAT
Improved exact algorithms for MAX-SAT
An Empirical Study of MAX-2-SAT Phase Transitions
A randomized algorithm for 3-SAT
Solving connected dominating set faster than \(2^n\)
Comparing the succinctness of monadic query languages over finite trees
Theory and Applications of Satisfiability Testing
UnitWalk: A new SAT solver that uses local search guided by unit clause elimination
Solving NP-Complete Problems with Quantum Search
A new upper bound for \(( n , 3)\)-MAX-SAT
Exploiting partial knowledge of satisfying assignments
scientific article; zbMATH DE number 1670827 (Why is no real title available?)
An efficient fixed-parameter algorithm for 3-hitting set
Density condensation of Boolean formulas
Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences
Exact algorithms for MAX-SAT
A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles
A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
An improved exponential-time algorithm for k -SAT
An initial study of time complexity in infinite-domain constraint satisfaction
A full derandomization of Schöning's \(k\)-\textsc{SAT} algorithm
Local reductions
Strong ETH and resolution via games and the multiplicity of strategies
On converting CNF to DNF
An improved local search algorithm for 3-SAT
Chain, generalization of covering code, and deterministic algorithm for \(k\)-SAT
The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
An improved deterministic local search algorithm for 3-SAT
Local search algorithms for SAT: Worst-case analysis
Satisfiability certificates verifiable in subexponential time
An efficient local search method for random 3-satisfiability
Using heuristics to find minimal unsatisfiable subformulas in satisfiability problems
Local reduction
SAT local search algorithms: Worst-case study
Using small-scale quantum devices to solve algebraic equations
Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs
The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT
Improved agreeing-gluing algorithm
Algorithms for four variants of the exact satisfiability problem
The resolution complexity of random graph \(k\)-colorability
An improved upper bound for SAT
Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
scientific article; zbMATH DE number 1848397 (Why is no real title available?)
A note on the complexity of minimum dominating set

This page was built for publication: A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.

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