文章基本信息

标题：Improved Upper Bounds for 3-SAT
本地全文：下载
作者：Kazuo Iwama, Suguru Tamaki
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
关键词：CNF Satisfiability , complexity , Probabilistic algorithm