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

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 $\mathcal{O}\mathrm{(}{1.3071}^{\mathit{n}}\mathrm{)}$ . Its bound degenerates when the number of solutions increases. In 1999, Schöning proved an $\mathcal{O}\mathrm{(}{1.3334}^{\mathit{n}}\mathrm{)}$ bound for 3-SAT. In 2003, Iwama and Tamaki combined both algorithms to yield an $\mathcal{O}\mathrm{(}{1.3238}^{\mathit{n}}\mathrm{)}$ bound. We tweak the PPSZ-Bound to get a slightly better contribution to the combined algorithm and prove an $\mathcal{O}\mathrm{(}{1.32216}^{\mathit{n}}\mathrm{)}$ bound.