Blum Complexity Measures

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:

1. Φ(M,x) is finite if and only if M(x) halts, and
2. There is a computable procedure that given (M,x,r) can decide if Φ(M,x)=r.

These are known as Blum axioms and measures that fulfill them are known as Blum complexity measures. They were developed by Manuel Blum in the late 1960's.

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.

1. The only truly interesting Blum measures are time and space.
2. The functions and languages that one gets out of the speed-up, gap and related theorems are usually quite large and artificial.
3. 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.

In 1991 I saw Manuel Blum give a talk discussing a new complexity measure, something about mind changes, that did not fulfill his axioms. So we had a Blum complexity measure that was not a Blum complexity measure and as Douglas Adams would say Manuel Blum "promptly vanishes in a puff of logic." [Just kidding-we like Manuel]