Journal
SIAM JOURNAL ON COMPUTING
Volume 42, Issue 3, Pages 1218-1244Publisher
SIAM PUBLICATIONS
DOI: 10.1137/10080703X
Keywords
lower bounds; improved exponential algorithms; exact algorithms; time-space trade-offs; circuit complexity
Funding
- NSF [CCF-0832797, DMS-0835373]
- Josef Raviv Memorial Fellowship
Ask authors/readers for more resources
The P vs. NP problem arose from the question of whether exhaustive search is necessary for problems with short verifiable solutions. We do not know if even a slight algorithmic improvement over exhaustive search is universally possible for all NP problems, and to date no major consequences have been derived from the assumption that an improvement exists. We show that there are natural NP and BPP problems for which minor algorithmic improvements over the trivial deterministic simulation already entail lower bounds such as NEXP not subset of P/poly and LOGSPACE not equal NP. These results are especially interesting given that similar improvements have been found for many other hard problems. Optimistically, one might hope our results suggest a new path to lower bounds; pessimistically, they show that carrying out the seemingly modest program of finding slightly better algorithms for all search problems may be extremely difficult (if not impossible). We also prove unconditional superpolynomial time-space lower bounds for improving on exhaustive search: there is a problem verifiable with k(n) length witnesses in O(n(a)) time (for some a and some function k(n) <= n) that cannot be solved in k(n)(c)n(a+o(1)) time and k(n)(c)n(o(1)) space, for every c >= 1. While such problems can always be solved by exhaustive search in O(2(k(n))n(a)) time and O(k(n)+n(a)) space, we can prove a superpolynomial lower bound in the parameter k(n) when space usage is restricted.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available