About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
STOC 2010
Conference paper
Improving exhaustive search implies superpolynomial lower bounds
Abstract
The P vs NP problem arose from the question of whether exhaustive search is necessary for problems with short verifiable solutions. We still 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 ⊈ P/poly and LOGSPACE ≠ 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(na) time (for some a and some function k(n) ≤ n) that cannot be solved in k(n)cn a+o(1) time and k(n)cno(1) space, for every c ≥ 1. While such problems can always be solved by exhaus- tive search in O(2 k(n)na) time and O(k(n) + na) space, we can prove a superpolynomial lower bound in the parameter k(n) when space usage is restricted. © 2010 ACM.