zbMATH — the first resource for mathematics

On the complexity of \(k\)-SAT. (English) Zbl 0990.68079
Summary: 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\geq 3\). Here exponential time means \(2^{\delta n}\) for some \(\delta> 0\). In this paper, assuming that, for \(k\geq 3\), \(k\)-SAT requires exponential time complexity, we show that the complexity of \(k\)-SAT increases as \(k\) increases. More precisely, for \(k\geq 3\), define \(s_k= \inf\{\delta\): there exists \(2^{\delta n}\) algorithm for solving \(k\)-SAT}. Define ETH (Exponential-Time Hypothesis) for \(k\)-SAT as follows: for \(k\geq 3\), \(s_k> 0\). In this paper, we show that \(s_k\) is increasing infinitely often assuming ETH for \(k\)-SAT. Let \(s_\infty\) be the limit of \(s_k\). We will in fact show that \(s_k\leq (1-d/k)s_\infty\) 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^{\varepsilon n}\) \(k'\)-CNFs in fewer variables for some \(k'\geq k\) and arbitrarily small \(\varepsilon> 0\). We also show that such a disjunction can be computed in time \(2^{\varepsilon n}\) for arbitrarily small \(\varepsilon> 0\).

68Q25 Analysis of algorithms and problem complexity
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: DOI
[1] Alon, N.; Spencer, J.; Erdős, P., The probabilistic method, (1992), Wiley New York
[2] Beigel, R.; Eppstein, R., 3-coloring in time O(1.3446n) time: a no-MIS algorithm, Proceedings of the 36th annual IEEE symposium on foundations of computer science, (1995), p. 444-453 · Zbl 0938.68940
[3] Crawford, J.M.; Auton, L.D., Experimental results on the crossover point in random 3SAT, Artificial intelligence, 81, (1996)
[4] E. A. Hirsch, Two new upper bounds for SAT, in, SIAM Conference on Discrete Algorithms, 1997.
[5] R. Impagliazzo, R. Paturi, and F. Zane, Which problems have strongly exponential complexity, in 1998 Annual IEEE Symposium on Foundations of Computer Science, pp. 653-662. · Zbl 1006.68052
[6] Jian, T., An O(20.304n) algorithm for solving maximum independent set problem, IEEE trans. comput., 35, 847-851, (1986) · Zbl 0606.68062
[7] O. Kullmann, and, H. Luckhardt, Deciding propositional tautologies: algorithms and their complexity, submitted.
[8] Lawler, E., A note on the complexity of the chromatic number problem, Inform. process. lett., 5, 66-67, (1976) · Zbl 0336.68021
[9] Monien, B.; Speckenmeyer, E., Solving satisfiability in less than 2^n steps, Discrete appl. math., 10, 287-295, (1985) · Zbl 0603.68092
[10] Paturi, R.; Pudlák, P.; Zane, F., Satisfiability coding lemma, Proceedings of the 38th annual IEEE symposium on foundations of computer science, (1997), p. 566-574
[11] Paturi, R.; Pudlák, P.; Saks, M.; Zane, F., An improved exponential-time algorithm for k-SAT, 1998 annual IEEE symposium on foundations of computer science, (1998), p. 628-637
[12] Robson, J., Algorithms for maximum independent sets, J. algorithms, 7, 425-440, (1986) · Zbl 0637.68080
[13] Schiermeyer, I., Solving 3-satisfiability in less than 1.579^n steps, Selected papers from CSL ’92, Lecture notes in computer science, 702, (1993), Springer-Verlag Berlin/New York, p. 379-394 · Zbl 0788.68066
[14] Schiermeyer, I., Pure literal look ahead: an O(1.497n) 3-satisfiability algorithm, Technical report, university of Köln, (1996)
[15] Schöning, U., A probabilistic algorithm for k-SAT and constraint satisfaction problems, 1999 annual IEEE symposium on foundations of computer science, (1999), p. 410-414
[16] B. Selman, Personal communication, 1999.
[17] Shindo, M.; Tomita, E., A simple algorithm for finding a maximum clique and its worst-case time complexity, Systems comput. Japan, 21, 1-13, (1990)
[18] Tarjan, R.; Trojanowski, A., Finding a maximum independent set, SIAM J. comput., 6, 537-546, (1977) · Zbl 0357.68035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.