Which Problems Have Strongly Exponential Complexity?

Abrahamson, 1995, Fixed parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues

Ajtái, 1983, Σ11-formulae on finite structures, Ann. Pure Appl. Logic, 24, 1, 10.1016/0168-0072(83)90038-6

Alon, 1992

Arora, 1996, Polynomial time approximation schemes for Euclidean TSP and other geometric problems

Arora, 1992, Proof verification and hardness of approximation problems

Bellare, 1996, Proof checking and approximation: Towards tight results, Complexity theory column, Sigact News, 27

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

Boppana, 1990, The complexity of finite functions

Cormen, 1990

Feige, 1991, Approximating Clique is almost NP-complete

T. Feder, and, R. Motwani, Worst-case time bounds for coloring and satisfiability problems, manuscript, September 1998.

Furst, 1984, Parity, circuits, and the polynomial time hierarchy, Math. Systems Theory, 17, 13, 10.1007/BF01744431

Garey, 1979

Håstad, 1986, Almost optimal lower bounds for small depth circuits

Håstad, 1996, Clique is hard to approximate within n1−ε

Håstad, 1997, Some optimal inapproxibility results

Håstad, 1993, Top-down lower bounds for depth 3 circuits

Hirsch, 1998, Two new upper bounds for SAT

O. Kullmann, and, H. Luckhard, Deciding propositional tautologies: Algorithms and their complexity, submitted.

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

R. Paturi, P. Pudlák, and F. Zane, Satisfiability coding lemma, in Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, October 1997, pp. 567–574.

R. Paturi, P. Pudlák, M. E. Saks, and F. Zane, An improved exponential-time algorithm for k-SAT, in 1998 Annual IEEE Symposium on Foundations of Computer Science, pp. 628–637.

Paturi, 1997, Exponential lower bounds on depth 3 Boolean circuits

Papadimitriou, 1991, Opimization, approximation and complexity classes, J. Comput. System Sci., 43, 425, 10.1016/0022-0000(91)90023-X

Razborov, 1986, Lower bounds on the size of bounded depth networks over a complete basis with logical addition, Mat. Zameti, 41, 598

Sauer, 1972, On the density of families of sets, J. Combin. Theory Ser. A, 13, 145, 10.1016/0097-3165(72)90019-2

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. Workshop on the satisfiability problem, technical report, 96

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

Smolensky, 1987, Algebraic methods in the theory of lower bounds for Boolean circuit complexity

Stearns, 1990, Power indices and easier hand problems, Math. Systems Theory, 23, 209, 10.1007/BF02090776

Johnson, 1999, What are the least tractable instances of Max Clique?

Valiant, 1977, Graph-theoretic arguments in low-level complexity, 53

Van Lint, 1992

Vapnik, 1971, On the uniform convergence of relative frequencies of events to their probabilities, Theory Probab. Appl., 16, 264, 10.1137/1116025

Yao, 1985, Separating the polynomial hierarchy by oracles

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

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