ECCC-Report TR03-054https://eccc.weizmann.ac.il/report/2003/054Comments and Revisions published for TR03-054en-usTue, 08 Jul 2003 18:02:11 +0300
Paper TR03-054
| 3-SAT in RTIME(O(1.32793^n)) - Improving Randomized Local Search by Initializing Strings of 3-Clauses |
Daniel Rolf
https://eccc.weizmann.ac.il/report/2003/054This 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.
Tue, 08 Jul 2003 18:02:11 +0300https://eccc.weizmann.ac.il/report/2003/054