On the Complexity of k-SAT

Alon, 1992

Beigel, 1995, 3-Coloring in time O(1.3446n) time: a no-MIS algorithm

Crawford, 1996, Experimental results on the crossover point in random 3SAT, Artificial Intelligence, 81, 10.1016/0004-3702(95)00046-1

E. A. Hirsch, Two new upper bounds for SAT, in, SIAM Conference on Discrete Algorithms, 1997.

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.

Jian, 1986, An O(20.304n) algorithm for solving maximum independent set problem, IEEE Trans. Comput., 35, 847, 10.1109/TC.1986.1676847

O. Kullmann, and, H. Luckhardt, Deciding propositional tautologies: algorithms and their complexity, submitted.

Lawler, 1976, A note on the complexity of the chromatic number problem, Inform. Process. Lett., 5, 66, 10.1016/0020-0190(76)90065-X

Monien, 1985, Solving satisfiability in less than 2n steps, Discrete Appl. Math., 10, 287, 10.1016/0166-218X(85)90050-2

Paturi, 1997, Satisfiability coding lemma

Paturi, 1998, An improved exponential-time algorithm for k-SAT

Robson, 1986, Algorithms for maximum independent sets, J. Algorithms, 7, 425, 10.1016/0196-6774(86)90032-5

Schiermeyer, 1993, Solving 3-satisfiability in less than 1.579n steps, 702

Schiermeyer, 1996, Pure literal look ahead: an O(1.497n) 3-satisfiability algorithm, Technical Report, University of Köln

Schöning, 1999, A probabilistic algorithm for k-SAT and constraint satisfaction problems

B. Selman, Personal communication, 1999.

Shindo, 1990, A simple algorithm for finding a maximum clique and its worst-case time complexity, Systems Comput. Japan, 21, 1, 10.1002/scj.4690210301

Tarjan, 1977, Finding a maximum independent set, SIAM J. Comput., 6, 537, 10.1137/0206038