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

Article type: Research Article

Authors: Rolf, Daniel

Affiliations: Humboldt-University Berlin, Department of Computer Science, Logic in Computer Science, Unter den Linden 6, 10099 Berlin, Germany. E-mail: rolf@informatik.hu-berlin.de

Keywords: 3-SAT, worst case bound, bounded resolution, randomized local search

DOI: 10.3233/SAT190005

Journal: Journal on Satisfiability, Boolean Modeling and Computation, vol. 1, no. 2, pp. 111-122, 2006

Received 1 January 2006
|
Revision received 1 October 2006
|
Published: 1 November 2006
Get PDF open access

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.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.

Show less