Compression theorem

On this page

Compression theorem

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.

We don't have any images related to Compression theorem yet.

You can add one yourself here.

We don't have any YouTube videos related to Compression theorem yet.

You can add one yourself here.

We don't have any PDF documents related to Compression theorem yet.

You can add one yourself here.

We don't have any Books related to Compression theorem yet.

You can add one yourself here.

We don't have any archived web articles related to Compression theorem yet.

You can submit a link to a page to archive here.

Given a Gödel numbering φ {\displaystyle \varphi } of the computable functions and a Blum complexity measure Φ {\displaystyle \Phi } where a complexity class for a boundary function f {\displaystyle f} is defined as

C ( f ) := { φ i ∈ R ( 1 ) | ( ∀ ∞ x ) Φ i ( x ) ≤ f ( x ) } . {\displaystyle \mathrm {C} (f):=\{\varphi _{i}\in \mathbf {R} ^{(1)}|(\forall ^{\infty }x)\,\Phi _{i}(x)\leq f(x)\}.}

Then there exists a total computable function f {\displaystyle f} so that for all i {\displaystyle i}

D o m ( φ i ) = D o m ( φ f ( i ) ) {\displaystyle \mathrm {Dom} (\varphi _{i})=\mathrm {Dom} (\varphi _{f(i)})}

and

C ( φ i ) ⊊ C ( φ f ( i ) ) . {\displaystyle \mathrm {C} (\varphi _{i})\subsetneq \mathrm {C} (\varphi _{f(i)}).}

Salomaa, Arto (1985), "Theorem 6.9", Computation and Automata, Encyclopedia of Mathematics and Its Applications, vol. 25, Cambridge University Press, pp. 149–150, ISBN 9780521302456.
Zimand, Marius (2004), "Theorem 2.4.3 (Compression theorem)", Computational Complexity: A Quantitative Perspective, North-Holland Mathematics Studies, vol. 196, Elsevier, p. 42, ISBN 9780444828415.