A resource-bounded version of the statement "no algorithm recognizes all non-halting Turing machines" is equivalent to an infinitely-often (i.o.) superpolynomial speedup for the time required to accept any coNP-complete language and also equivalent to a superpolynomial speedup in proof length in propositional proof systems for tautologies, each of which implies P!=NP. This suggests a correspondence between the properties 'has no algorithm at all' and 'has no best algorithm' which seems relevant to open problems in computational and proof complexity.

Theor. Comput. Sci. 412 (2011) 478-481. 10.1016/j.tcs.2010.09.029

Informally, a language L has speedup if, for any Turing machine (TM) for L, there exists one that is better. Blum showed that there are computable languages that have almost-everywhere speedup. These languages were unnatural in that they were constructed for the sole purpose of having such speedup. We identify an intuitive condition which, like several others in the literature, implies that accepting any coNP-complete language has an infinitely-often (i.o.) superpolynomial speedup. We also exhibit a natural problem which unconditionally has a weaker type of i.o. speedup based upon whether the full input is read. Neither speedup pertains to the worst case.

Drops the claim that there is a p-optimal TM accepting any NP-complete problem.

Informally, a language L has speedup if, for any Turing machine for L, there exists one that is better. Blum showed that there are computable languages that have almost-everywhere speedup. These languages were unnatural in that they were constructed for the sole purpose of having such speedup. We identify 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 NP!=coNP. We also exhibit a natural problem which unconditionally has a weaker type of i.o. speedup based upon whether the full input is read. Neither speedup pertains to the worst case.