Name
Abstract | ||
|---|---|---|
In [Sch99], Sch枚ning proposed a simple yet efficient randomized algorithm for solving the k-SAT problem. In the case of 3-SAT, the algorithm has an expected running time of poly(n) 驴 (4/3)n = O(1.3334n) when given a formula F on n variables. This was the up to now best running time known for an algorithm solving 3-SAT. Here, we describe an algorithm which improves upon this time bound by combining an improved version of the above randomized algorithm with other randomized algorithms. Our new expected time bound for 3-SAT is O(1.3302n). |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1007/3-540-45841-7_15 | STACS |
Keywords | Field | DocType |
k-sat problem,randomized algorithm,efficient randomized algorithm,n variable,new expected time,improved version,probabilistic 3-sat algorithm,formula f | Randomized algorithm,Discrete mathematics,Combinatorics,Computer science,Boolean satisfiability problem,Propositional calculus,Algorithm,Probabilistic logic,Freivalds' algorithm | Conference |
ISBN | Citations | PageRank |
3-540-43283-3 | 42 | 5.10 |
References | Authors | |
8 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thomas Hofmeister | 1 | 74 | 9.91 |
| Uwe Schöning | 2 | 998 | 105.69 |
| Rainer Schuler | 3 | 66 | 9.46 |
| Osamu Watanabe | 4 | 960 | 104.55 |