July Edition As a graduate student, Manuel Blum wanted to study computational complexity freed from any specific machine model. His paper set the tone for much of complexity of the late 60's.

Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, JACM 1967. Blum defined a resource measure as any partially computable function Φ

_{M}(think time) of a machine M that fulfilled some simple axioms.- For all x, M(x) halts iff Φ
_{M}(x) halts. - The language
{<M,x,m> | Φ
_{M}(x)=m} is computable.

*any*reasonable model of Turing machine would fulfill these axioms. He also noticed that space complexity also fulfills the axioms. Though the axioms are very general, Blum shows their power with the speed-up theorem.**Speed-Up Theorem:**For every computable function r, there is a language L such that if M accepts L there is an N accepting L with r(x,Φ_{N}(x))≤Φ_{M}(x) for almost all x.For example there is some language L such that if any algorithm computes L in t(n) steps there is another algorithm computing L in log t(n) steps. This might seem to violate the time hierarchy but t(n) does not have the time constructibility needed for the hierarchy. Blum also showed there was a language that couldn't be sped up much and a computably-bounded relationship between any two abstract resource measures.

Borodin and Trakhtenbrot independently proved the gap theorem for abstract complexity measures.

**Gap Theorem:**Given any computable function g(x)≥x there is a recursive function t(x) such that if Φ_{M}(x)≤g(t(x)) for all x then there is an N accepting the same language as M with Φ_{N}(x)≤t(x) for almost all x.In particular there is a function t(n) such that DTIME(t(n))=DTIME(2

^{t(n)}) and thus DTIME(t(n))=DSPACE(t(n)).McCreight and Meyer proved the union theorem.

**Union Theorem:**Let t_{1}, t_{2}, … be a computable enumeration of increasing resource bounds. There is a computable function t such that the following are equivalent for all M.- For some i and almost all x,
Φ
_{M}(x)≤t_{i}(x). - For almost all x, &Phi
_{M}(x)≤t(x).

_{1}and t_{2}such that DTIME(t_{1}(n)) is equal to P and DTIME(t_{2}(n)) is exactly the primitive recursive languages.McCreight and Meyer also give an honesty theorem showing that computable t there is (in a weak sense) a time-constructible t' such that languages computable with resource bound t are equal to languages computable with resource bound t'.

After the P versus NP problem was popularized by Cook and Karp in 1971, the focus of complexity went to polynomial-time (which also was machine independent) and away from abstract complexity.

--

Posted by Lance to Computational Complexity at 8/08/2005 04:46:00 PM- For all x, M(x) halts iff Φ