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,1^t >| 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)};

T_M 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)=T_M(N',x',1^t) 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',1^t) is NOT in BHP. Hence a TM that first checks if the input is of the form (N',x',1^t), 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 1^t 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.