- 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

(*) 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.

--

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