This paper presents a new upper bound for the k -satisfiability problem. For small k 's, especially for k = 3 , there have been a lot of algorithms which run significantly faster than the trivial 2 n bound. The following list summarizes those algorithms where a constant c means that the algorithm runs in time O ( c n ) . Roughly speaking most algorithms are based on Davis-Putnam. cite{Sch99} is the first local search algorithm which gives a guaranteed performance for general instances and cite{DGH+02}, cite{HSSW02} and cite{BS03} follow up this Sch"oning's approach. 3-SAT | 4-SAT | 5-SAT | 6-SAT | type | ref. ------------------------------------------------- 1.782 | 1.835 | 1.867 | 1.888 | det. | [PPZ97] 1.618 | 1.839 | 1.928 | 1.966 | det. | [MS85] 1.588 | 1.682 | 1.742 | 1.782 | prob. | [PPZ97] 1.579 | - | - | - | det. | [Sch92] 1.505 | - | - | - | det. | [Kul99] 1.481 | 1.6 | 1.667 | 1.75 | det. | [DGH+02] 1.362 | 1.476 | 1.569 | 1.637 | prob. | [PPSZ98] 1.334 | 1.5 | 1.6 | 1.667 | prob. | [Sch99] 1.3302 | - | - | - | prob. | [HSSW02] 1.3290 | - | - | - | prob. | [BS03] 1.324 | 1.474 | - | - | prob. | [*] Our new bounds are denoted by [*] in the above list, namely we prove that for any satisfiable n -variable 3-CNF (4-CNF) formula F , there exists a randomized algorithm that finds a satisfying assignment of F in expected running time O (1 32 4 n ) ( O (1 47 4 n ) ). The basic idea is to combine two existing algorithms, the one by Paturi, Pudl'ak, Saks and Zane cite{PPSZ98} and the other by Sch"oning cite{Sch99}. It should be noted, however, that simply running the two algorithms independently does not seem to work. Also, our approach can escape one of the most complicated portions in the analysis of cite{PPSZ98}. In this paper we focus on the 3-SAT case; the 4-SAT case is very similar and may be omitted. The same approach does not improve the bounds for 5-SAT or more.
展开▼
