Paper Info
Title
Solving random satisfiable 3CNF formulas in expected polynomial time
Abstract
We present an algorithm for solving 3SAT instances. Several algorithms have been proved to work whp (with high probability) for various SAT distributions. However, an algorithm that works whp has a drawback. Indeed for typical instances it works well, however for some rare inputs it does not provide a solution at all. Alternatively, one could require that the algorithm always produce a correct answer but perform well on average. Expected polynomial time formalizes this notion. We prove that for some natural distribution on 3CNF formulas, called planted 3SAT, our algorithm has expected polynomial (in fact, almost linear) running time. The planted 3SAT distribution is the set of satisfiable 3CNF formulas generated in the following manner. First, a truth assignment is picked uniformly at random. Then, each clause satisfied by it is included in the formula with probability p. Extending previous work for the planted 3SAT distribution, we present, for the first time for a satisfiable SAT distribution, an expected polynomial time algorithm. Namely, it solves all 3SAT instances, and over the planted distribution (with p = d/n2, d 0 a sufficiently large constant) it runs in expected polynomial time. Our results extend to k-SAT for any constant k.
Year
DOI
Venue
2006
10.1145/1109557.1109608
SODA
Keywords
Field
DocType
expected polynomial time algorithm,high probability,natural distribution,satisfiable sat distribution,constant k,expected polynomial time,random satisfiable,previous work,various sat distribution,correct answer,probability p,np hard,polynomial time,nucleolus,satisfiability
Flow game,Discrete mathematics,Combinatorics,Polynomial,Boolean satisfiability problem,Degree of a polynomial,Matrix polynomial,Time complexity,Mathematics
Conference
ISBN
Citations 
PageRank 
0-89871-605-5
15
1.19
References 
Authors
24
2
Name
Order
Citations
PageRank
michael krivelevich11688179.90
Dan Vilenchik214313.36