Improving Exhaustive Search Implies Superpolynomial Lower Bounds
- 1 January 2013
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 42 (3), 1218-1244
- https://doi.org/10.1137/10080703x
Abstract
No abstract availableThis publication has 37 references indexed in Scilit:
- The Complexity of Satisfiability of Small Depth CircuitsLecture Notes in Computer Science, 2009
- Tight lower bounds for certain parameterized NP-hard problemsInformation and Computation, 2005
- On the existence of subexponential parameterized algorithmsJournal of Computer and System Sciences, 2003
- A Probabilistic-Time Hierarchy Theorem for “Slightly Non-uniform” AlgorithmsLecture Notes in Computer Science, 2002
- Sharply Bounded Alternation and Quasilinear TimeTheory of Computing Systems, 1998
- On the Amount of Nondeterminism and the Power of VerifyingSIAM Journal on Computing, 1997
- Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analoguesAnnals of Pure and Applied Logic, 1995
- BPP has subexponential time simulations unlessEXPTIME has publishable proofscomputational complexity, 1993
- Nondeterminism within $P^ * $SIAM Journal on Computing, 1993
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975