Speedup for natural problems and noncomputability
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 (paddable) coNP-complete language and also equivalent to a superpolynomial speedup in proof length in propositional proof systems for tautologies, each of which implies P not equal 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. (c) 2010 Elsevier B.V. All rights reserved.
propositional proof system speedability speedup conp-complete optimal algorithm