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 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 exhaustive search in O(2k(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. © 2013 Society for Industrial and Applied Mathematics.