Name
Abstract | ||
|---|---|---|
The problem of k-SAT is to determine if the given k-CNF has a satisfying solution. It is a celebrated open question as to whether it requires exponential time to solve k-SAT for k/spl ges/3. Define s/sub k/ (for k/spl ges/3) to be the infimum of {/spl delta/: there exists an O(2/sup /spl delta/n/) algorithm for solving k-SAT}. Define ETH (Exponential-Time Hypothesis) for k-SAT as follows: for k/spl ges/3, s/sub k/>0. In other words, for k/spl ges/3, k-SA does not have a subexponential-time algorithm. In this paper we show that s/sub k/ is an increasing sequence assuming ETH for k-SAT: Let s/sub /spl infin// be the limit of s/sub k/. We in fact show that s/sub k//spl les/(1-d/k) s/sub /spl infin// for some constant d>0. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1109/CCC.1999.766282 | Proceedings. Fourteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat.No.99CB36317) |
Keywords | Field | DocType |
k-SAT complexity,exponential time,subexponential-time algorithm | Discrete mathematics,Combinatorics,Exponential function,Infimum and supremum,Mathematics,Computational complexity theory | Conference |
ISSN | ISBN | Citations |
1093-0159 | 0-7695-0075-7 | 28 |
PageRank | References | Authors |
1.62 | 9 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Russell Impagliazzo | 1 | 5444 | 482.13 |
| Ramamohan Paturi | 2 | 1260 | 92.20 |