Logik in der Informatik
Prof. Dr. Martin Grohe

Institut für Informatik

Mitarbeiterseminar Logik in der Informatik

Freitag, 20. Januar 2006, 11:15 Uhr
RUD 25, Raum 3.101

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

Daniel Rolf
Humboldt-Universität zu Berlin

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). Their bound degenerates when the number of solutions increases. In 1999, Schöning proved a bound of O(1.3334n) 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.

Zurück zur Vortragsübersicht 

Last modified: Mon Jan 16 10:45:56 CET 2006
André Hernich