Which Problems Have Strongly Exponential Complexity?
Top Cited Papers
- 31 December 2001
- journal article
- Published by Elsevier BV in Journal of Computer and System Sciences
- Vol. 63 (4), 512-530
- https://doi.org/10.1006/jcss.2001.1774
Abstract
No abstract availableKeywords
This publication has 23 references indexed in Scilit:
- Polynomial time approximation schemes for Euclidean TSP and other geometric problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Approximating clique is almost NP-completePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Proof verification and the hardness of approximation problemsJournal of the ACM, 1998
- Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analoguesAnnals of Pure and Applied Logic, 1995
- Top-down lower bounds for depth-three circuitscomputational complexity, 1995
- The Complexity of Finite FunctionsPublished by Elsevier BV ,1990
- Almost optimal lower bounds for small depth circuitsPublished by Association for Computing Machinery (ACM) ,1986
- Solving satisfiability in less than 2n stepsDiscrete Applied Mathematics, 1985
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984
- ∑11-Formulae on finite structuresAnnals of Pure and Applied Logic, 1983