A full derandomization of schöning's k-SAT algorithm

DOI10.1145/1993636.1993670zbMath1288.68245arXiv1008.4067MaRDI QIDQ5419094

Robin A. Moser, Dominik 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

deterministic; derandomization; Schöning's algorithm; \(k\)-\textsc{SAT}; \textsc{SAT}

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W05: Nonnumerical algorithms

68R05: Combinatorics in computer science

Related Items

Unnamed Item, Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT, A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles, Unnamed Item, Unnamed Item, Strong partial clones and the time complexity of SAT problems, A satisfiability algorithm and average-case hardness for formulas over the full binary basis, Derandomizing the HSSW algorithm for 3-SAT, An exact exponential time algorithm for counting bipartite cliques, An initial study of time complexity in infinite-domain constraint satisfaction, The string guessing problem as a method to prove lower bounds on the advice complexity, 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