In Hromkovi?\'s Algorithmics for Hard Problems (2nd edition) there is this theor

Question

In Hromkovi?'s Algorithmics for Hard Problems (2nd edition) there is this theorem (2.3.3.3, page 117):

There is a (decidable) decision problem P such that for every algorithm A that solves P there is another algorithm A? that also solves P and additionally fulfills
??n?N.TimeA?(n)=log2TimeA(n)

TimeA(n) is the worst-case runtime of A on inputs of size n and ?? means "for all but finitely many".

A proof is not given and we have no idea how to go about this; it is quite counter-intuitive, actually. How can the theorem be proven?

Explanation / Answer

It seems to be a simple case of Blum's Speedup Theorem:

Given a Blum complexity measure (?,?) and a total computable function f with two parameters, then there exists a total computable predicate g (a Boolean valued computable function) so that for every program i for g, there exists a program j for g so that for almost all x

f(x,?j(x))??i(x)

Just let the the complexity measure be the time complexity measure (i.e. ?e(x) is the time complexity of the Turing machine with code e) and let f(x,y)=2y.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.