Wednesday, July 08, 2009

Speedup for Natrual Problems (Guest Post)

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.


  1. Kool! You can always presume the O(1) oracle algorithm, I know I do, and wait for it to appear. I too was naïvly onto this for some time, from when my "lab partner" asked how to know the way back and the answer was put it on the stack and the way is already sorted.

    Thesis: G(O(f(n)))=O(1)
    Example: Switch models and at once O(n) is O(1)
    Hence all computable calculations already can prepare O(1)


  2. There is now a blog on Speedup in Computational Complexity here: