Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-054 | 2nd July 2003 00:00

3-SAT in RTIME(O(1.32793^n)) - Improving Randomized Local Search by Initializing Strings of 3-Clauses


Authors: Daniel Rolf
Publication: 8th July 2003 18:02
Downloads: 1077


This paper establishes a randomized algorithm that finds a satisfying assignment for a satisfiable formula $F$ in 3-CNF in $O(1.32793^n)$ expected running time. The algorithms is based on the analysis of so-called strings, which are sequences of 3-clauses where non-succeeding clauses do not share a variable and succeeding clauses share one or two variables. One the one hand, if there are not many independent strings, we can solve $F$ with a decent success probability, but on the other hand, if there are many strings, we use them to improve the running time of Schöning's 3-SAT algorithm. Within a string, propagation of unit clauses is used to find successors.

ISSN 1433-8092 | Imprint