You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

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


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