A full derandomization of Schöning's k-\textsc{SAT} algorithm

DOI10.1145/1993636.1993670MaRDI QIDQ5419094zbMATH OpenOpenAlexFDO

Authors Robin A. Moser, D. Scheder

Publication date 5 June 2014

Published in Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.4067

zbMATH Keywords

\(k\)-\textsc{SAT}\textsc{SAT}derandomizationdeterministicSchöning's algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Nonnumerical algorithms (68W05)

Abstract: Schoening in 1999 presented a simple randomized algorithm for k-SAT with running time O(a^n * poly(n)) for a = 2(k-1)/k. We give a deterministic version of this algorithm running in time O((a+epsilon)^n * poly(n)), where epsilon > 0 can be made arbitrarily small.

Recommendations

• Randomized algorithms for 3-SAT
• Theory and Applications of Satisfiability Testing
• scientific article; zbMATH DE number 2086385
• Theory and Applications of Satisfiability Testing
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.

Cited in

(25)

• A combinatorial analysis for the critical clause tree
• A new upper bound for \(( n , 3)\)-MAX-SAT
• New exact algorithms for the 2-constraint satisfaction problem
• Solving SCS for bounded length strings in fewer than \(2^n\) steps
• Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT
• Using small-scale quantum devices to solve algebraic equations
• Satisfiability certificates verifiable in subexponential time
• Basic Terminology, Notation and Results
• Strong partial clones and the time complexity of SAT problems
• Strong Refutation Heuristics for Random k-SAT
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• An exact exponential time algorithm for counting bipartite cliques
• scientific article; zbMATH DE number 1738648 (Why is no real title available?)
• Chain, generalization of covering code, and deterministic algorithm for \(k\)-SAT
• Solving systems of polynomial equations over GF(2) by a parity-counting self-reduction
• An initial study of time complexity in infinite-domain constraint satisfaction
• A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles
• Width-parametrized SAT: time-space tradeoffs
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• A satisfiability algorithm for \(\mathrm{AC}^0\)
• On conflict-free cuts: algorithms and complexity
• Local enumeration and majority lower bounds
• The string guessing problem as a method to prove lower bounds on the advice complexity
• Randomized algorithms for 3-SAT

This page was built for publication: A full derandomization of Schöning's \(k\)-\textsc{SAT} algorithm

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