DOC PREVIEW
Improving Exhaustive Search Implies Superpolynomial Lower Bounds

This preview shows page 1-2-3-26-27-28 out of 28 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

IntroductionMain ResultsImproved Algorithms Imply Circuit Lower BoundsImproved Algorithms Imply LOGSPACE=NP and Subexponential AlgorithmsUnconditional Lower BoundsA Nontrivial SimulationAn Overview of Our TechniquesPreliminariesNotation and BackgroundRelated WorkImproved Algorithms Imply Circuit Lower BoundsExtensionsExtremely Weak Derandomization Implies Circuit Lower BoundsFurther Improvements Imply LOGSPACE=NP and Subexponential proofs for QBFUnconditional Lower BoundsDiscussionAppendix: Proof of Lemma 3.1Appendix: Proof of Theorem 1.9A Remark About BarriersImproving Exhaustive Search ImpliesSuperpolynomial Lower BoundsRyan Williams∗IBM Almaden Research CenterMay 4, 2010AbstractThe P vs NP problem arose from the question of whether exhaustivesearch is necessary for problemswith short verifiable solutions. We do not know if even a slight algorithmic improvement over exhaustivesearch is universally possible for all NP problems, and to date no major consequences have been derivedfrom the assumption that an improvement exists.We show that there are natural NP and BPP problems for which minor algorithmic improvementsover the trivial deterministic simulation already entail lower bounds such as NEXP 6⊆ P/poly andLOGSPACE 6= NP. These results are especially interesting given that similar improvements have beenfound for many other hard problems. Optimistically, one might hope our results suggest a new pathto lower bounds; pessimistically, they show that carrying out the seemingly modest program of findingslightly 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 exhaustivesearch: there is a problem verifiable with k(n) length witnesses in O(na) time (for some a and somefunction k(n) ≤ n) that cannot be solved in k(n)cna+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 provea superpolynomiallower 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, supportedby NSF Grant CCF-0832797 (Expeditions in Computing) and NSF Grant DMS-0835373 (Pseudorandomness). At IBM, the authoris supported by the Josef Raviv Memorial Fellowship.1 IntroductionTo what extent can we avoid exhaustive search for generic search problems? This is one of the manyoffshoots of the P versus NP problem and it is the central question addressed in the area of exact algorithmsfor NP-hard problems.1The general message of this research has been that the trivial enumeration of allpossible solutions can be quantitatively improved upon for many problems (and their number is increasingevery year). The broad success of this program leads one to wonder if all NP problems allow some modestimprovement over brute-force search. More precisely, let V (x, y) be a verifier that runs on witnesses y oflength |x|cand takes O(|x|d) time. The runtime of exhaustive search for a witness is O(2|x|c|x|d). Canwe always find a witness in O(2.99|x|c|x|d)? What about O(2|x|c−log2|x||x|100d)? Can we approximate thefraction of witnesses that V accepts in this time? If V uses only s(n) space, can we find a witness inO(2.99|x|c|x|d) time and O(|x|100c+ s(n)) space? These questions are the focus of the present paper.Here we offer the first concrete evidence that the above minor improvements will be difficult to achievefor some problems. We do not rule out the possibility of these improvements; rather, we show that theywould already imply superpolynomial lower bounds in complexity theory. (Optimists might say we havegiven a new approach to proving class separations.) We show that the task of finding improved algorithms isconnected naturally to the task of proving superpolynomial lower bounds. Regardless of one’s complexity-theoretic worldview, our results show that one cannot simultaneously believe that “superpolynomial lowerbounds are far beyond our current techniques” and “simple tricks should suffice for improved exponentialalgorithms.”21.1 Main Results1.1.1 Improved Algorithms Imply Circuit Lower BoundsLet CIRCUIT SAT be the problem of finding a satisfying assignment to a Boolean circuit (over AND, OR,NOT gates). The CIRCUIT SAT problem is often the first NP-complete problem introduced in textbooks.Due to its applications in hardware/software verification and automated reasoning, the problem has beenextensively studied in many areas of computer science. (Although CNF satisfiability gets all the fanfare,most formulas obtained in practice start as Boolean circuits.) Clearly, for circuits with n input variables andpoly(n) gates, the problem can be solved in 2n· poly(n) time on any robust model of computation, and it isnot known how to solve the problem even slightly faster than this.3On a seemingly unrelated front, progress has been nearly nonexistent on proving superpolynomial circuitlower bounds for over a decade. It is known that the exponential-time version of Merlin-Arthur does nothave polynomial size circuits [BFT98], but it is not known how to improve the lower bound to even EXPNP,the class of problems solvable in exponential time with an NP oracle. Since it appears unlikely that NP doesnot have polynomial size circuits, this is indeed a frustrating state of affairs.These two lines of research can be related to each other in a striking way:1In fact, in G¨odel’s famous letter to Von Neumann, he posed precisely this question:“It would be interesting to know... in the case of finite combinatorial problems, how strongly in general the numberof steps vis-´a-vis dem blossen Probieren [the “bare trying” of solutions] can be reduced.” [Har89]2This was Mihai Patrascu’s eloquent way of putting it.3We use the poly(n) notation to denote O(nc) factors for a fixed c > 0 independent of n.1Theorem 1.1 Suppose there is a superpolynomial function s(n) such that CIRCUIT SAT on circuits with nvariables and nkgates can be solved in 2n· poly(nk)/s(n) time by a (co-non)deterministic algorithm, forall k. Then NEXP 6⊆ P/poly.That is, practically any nontrivial improvement over exhaustive search for CIRCUIT SAT (or nontrivialproofs of unsatisfiability) would already imply superpolynomial circuit lower bounds for nondeterministicexponential time. The best known deterministic algorithm for


Improving Exhaustive Search Implies Superpolynomial Lower Bounds

Download Improving Exhaustive Search Implies Superpolynomial Lower Bounds
Our administrator received your request to download this document. We will send you the file to your email shortly.
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 2 2 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?