speedup theorem
speedup theorem A theorem in complexity theory that, like the gap theorem, can be expressed in terms of abstract complexity measures (see Blum's axioms) but will be more understandable in the context of time.
Given any total recursive function r(n), there exists a recursive language L such that for any Turing machine M recognizing L, say within time bound S(n), there exists another Turing machine M′ that also recognizes L but within a time bound S′(n) that satisfies r(S′(n)) ← S(n)
for all but a finite number of values of n. Thus for this language there can be no fastest program.
Given any total recursive function r(n), there exists a recursive language L such that for any Turing machine M recognizing L, say within time bound S(n), there exists another Turing machine M′ that also recognizes L but within a time bound S′(n) that satisfies r(S′(n)) ← S(n)
for all but a finite number of values of n. Thus for this language there can be no fastest program.
More From encyclopedia.com
You Might Also Like
NEARBY TERMS
speedup theorem