Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Speedup for Natrual Problems (Guest Post)

Expand Messages
  • GASARCH
    Speedup for Natural Problems (Guest post by Hunter Monroe.) Blum proved speedup for an artificially constructed problem; this paper (arXiv link), (ECCC link)
    Message 1 of 1 , Jul 8, 2009
    • 0 Attachment
      Speedup for Natural Problems (Guest post by Hunter Monroe.)

      Blum proved speedup for an artificially constructed problem; this paper (arXiv link), (ECCC link) presents two results on speedup for natural problems (not in the worst case). First, it identifies a condition apparently only slightly stronger than P ≠ NP which implies that accepting any coNP-complete language has an infinitely-often (i.o.) superpolynomial speedup, and furthermore NP≠coNP.We define terms and then state the condition:

      BHP={<N,x,1t >| there is at least one accepting path of nondeterministic TM N on input x with t or fewer steps};

      HP={<N,x>| there is at least one accepting path of NTM N on input x (with no bound on the number of steps)};

      TM is the function that maps a string y to how many steps M(y) takes.

      The condition states:

      (*) For any deterministic Turing machine M accepting coBHP, there exists (N',x')∈coHP such that the function f(t)=TM(N',x',1t) is not bounded by any polynomial.
      (*) implies that any coNP-complete language has i.o. speedup: Let M be a TM that decides BHP. By (*) there is an N',x' such that, for all t, (N',x',1t) is NOT in BHP. Hence a TM that first checks if the input is of the form (N',x',1t), outputs NO if it is, and runs M if its not, has a superpolynomial advantage over M on infinitely many inputs. (*) shows that NP ≠ coNP since Schnorr showed there is an optimal M accepting any NP-complete language.

      Second, the paper shows that coBHP unconditionally has a weaker type of i.o. speedup. The intuition is that recognizing nonhalting N',x' is useful for an M accepting coBHP M can accept without reading the 1t part of the input. However, no M can avoid reading the full input for all N',x' as M could accept coHP which is not computably enumerable.

      In a similar spirit, the following conjectures suggest a nice linkage between the theories of complexity and computability: If there exists a poly time M accepting a coNP-complete language (for instance coBHP), then M can be modified to accept a language that is not c.e. (for instance coHP). If M can factor integers in polynomial time, then M can be modified to accept the set of true arithmetic statements.

      --
      Posted By GASARCH to Computational Complexity at 7/08/2009 10:00:00 AM

    Your message has been successfully submitted and would be delivered to recipients shortly.