On the Complexity of k-SAT

✍ Scribed by Russell Impagliazzo; Ramamohan Paturi

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 114 KB
• Volume: 62
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.2000.1727

✦ Synopsis

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.

2001 Academic Press

Although all NP-complete problems are equivalent as far as the existence of polynomial-time algorithm is concerned, there is wide variation in the worst-case complexity of known algorithms for these problems. For example, there have been several algorithms for maximum independent set , and the best of these takes time 1.2108 n in the worst-case . Recently, a 3-coloring algorithm with 1.3446 n worst-case time complexity is presented [2] and it is known that k-coloring can be solved in 2.442 n time [8]. However, it is not known what, if any, relationships exist among the worst-case complexities of various problems. In this paper, we examine the complexity of k-SAT, and derive a relationship that governs