Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-159 | 14th November 2005 00:00

Improved Bound for the PPSZ/Schöning-Algorithm for $3$-SAT

RSS-Feed




TR05-159
Authors: Daniel Rolf
Publication: 19th December 2005 22:16
Downloads: 3535
Keywords: 


Abstract:

The PPSZ Algorithm presented by Paturi, Pudlak, Saks, and Zane in 1998 has the nice feature that the only satisfying solution of a uniquely satisfiable $3$-SAT formula can be found in expected running time at most $O(1.3071^n)$. Its bound degenerates when the number of solutions increases. In 1999, Schöning proved an bound of $\O(1.3334^n)$ for $3$-SAT. In 2003, Iwama and Tamaki combined both algorithms to yield an $O(1.3238^n)$ bound. We tweak the PPSZ-Bound to get a slightly better contribution to the combined algorithm and prove an $\O(1.32216^n)$ bound.



ISSN 1433-8092 | Imprint