The Blum speed-up theorem states that there exists a computable language L such that if L is in time t(n) then L is in time log(t(n)). The log function can be replaced by any arbitrarily slowly growing computable function. Instead of time one can use space or any other measure Φ that fulfills these properties: - Φ(M,x) is finite if and only if M(x) halts, and
- There is a computable procedure that given (M,x,r) can decide if Φ(M,x)=r.

The Borodin-Trakhtenbrot Gap Theorem states that given any computable function g(n) (e.g. g(n)=2^n), there exists a function t(n) such that every language computable in time g(t(n)) is also computable in time t(n), i.e., there exists a gap between these time classes. Once again the theorem holds for any Blum complexity measure.

We don't see much of the Blum complexity measures these days for a few reasons.

- The only truly interesting Blum measures are time and space.
- The functions and languages that one gets out of the speed-up, gap and related theorems are usually quite large and artificial.
- Many measures that we are interested in today, like the number of random coins used by a probabilistic Turing machine, do not fulfill the Blum axioms.

--

Posted by Lance Fortnow to My Computational Complexity Web Log at 4/5/2004 08:06:26 AM