View Full Document

Improving Exhaustive Search Implies Superpolynomial Lower Bounds



View the full content.
View Full Document
View Full Document

3 views

Unformatted text preview:

Improving Exhaustive Search Implies Superpolynomial Lower Bounds Ryan Williams IBM Almaden Research Center May 4 2010 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 6 P poly and LOGSPACE 6 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 c na o 1 time and k n c no 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 This work originated while the author was a member of the Institute for Advanced Study in Princeton New Jersey supported by NSF Grant CCF 0832797 Expeditions in Computing and NSF Grant DMS 0835373 Pseudorandomness At IBM the author is supported by the Josef Raviv Memorial Fellowship 1 Introduction To what extent can we avoid exhaustive search for generic search problems This is one of the many offshoots of the P versus NP problem and it is the central question



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Improving Exhaustive Search Implies Superpolynomial Lower Bounds and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Improving Exhaustive Search Implies Superpolynomial Lower Bounds and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?