Name
Abstract | ||
|---|---|---|
The k - SAT problem is to determine if a given k -CNF has a satisfying assignment. It is a celebrated open question as to whether it requires exponential time to solve k -SAT for k ⩾3. Here exponential time means 2 δn for some δ >0. In this paper, assuming that, for k ⩾3, k -SAT requires exponential time complexity, we show that the complexity of k -SAT increases as k increases. More precisely, for k ⩾3, define s k =inf{ δ : there exists 2 δn algorithm for solving k -SAT}. Define ETH (Exponential-Time Hypothesis) for k -SAT as follows: for k ⩾3, s k >0. In this paper, we show that s k is increasing infinitely often assuming ETH for k -SAT. Let s ∞ be the limit of s k . We will in fact show that s k ⩽(1− d / k ) s ∞ for some constant d >0. We prove this result by bringing together the ideas of critical clauses and the Sparsification Lemma to reduce the satisfiability of a k -CNF to the satisfiability of a disjunction of 2 εn k ′-CNFs in fewer variables for some k ′⩾ k and arbitrarily small ε >0. We also show that such a disjunction can be computed in time 2 εn for arbitrarily small ε >0. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1006/jcss.2000.1727 | J. Comput. Syst. Sci. |
Keywords | Field | DocType |
time complexity,satisfiability | Discrete mathematics,Combinatorics,Exponential function,Existential quantification,3SUM,Satisfiability,Exponential complexity,Mathematics,Lemma (mathematics),Exponential time hypothesis | Journal |
Volume | Issue | ISSN |
62 | 2 | Journal of Computer and System Sciences |
ISBN | Citations | PageRank |
0-7695-0075-7 | 281 | 7.99 |
References | Authors | |
14 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Russell Impagliazzo | 1 | 281 | 7.99 |
| Ramamohan Paturi | 2 | 1260 | 92.20 |