Compression theorem explained

In computational complexity theory, the compression theorem is an important theorem about the complexity of computable functions.

The theorem states that there exists no largest complexity class, with computable boundary, which contains all computable functions.

Compression theorem

\varphi

of the computable functions and a Blum complexity measure

\Phi

where a complexity class for a boundary function

is defined as

C(f):=\{\varphi_i\inR⁽¹⁾|(\forall^inftyx)\Phi_i(x)\leqf(x)\}.

so that for all

Dom(\varphi_i)=Dom(\varphi_f(i))

and

C(\varphi_i)\subsetneqC(\varphi_f(i)).