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(*) 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_{M}(N',x',1^{t}) is not bounded by any polynomial.

^{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.

There is now a blog on Speedup in Computational Complexity here: http://speedupblogger.wordpress.com

ReplyDeleteHunter