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.

Compression theorem

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

: $\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$ so that for all $i$

: $\mathrm{Dom}(\varphi_i) = \mathrm{Dom}(\varphi_{f(i)})$

and

: $\mathrm{C}(\varphi_i) \subsetneq \mathrm{C}(\varphi_{f(i)}).$

References

{{citation|title=Computation and Automata|volume=25|series=Encyclopedia of Mathematics and Its Applications|first=Arto|last=Salomaa|authorlink=Arto Salomaa|publisher=Cambridge University Press|year=1985|isbn=9780521302456|contribution=Theorem 6.9|pages=149–150|url=https://books.google.com/books?id=IblDi626fBAC&pg=PA149}}.
{{citation|title=Computational Complexity: A Quantitative Perspective|volume=196|series=North-Holland Mathematics Studies|first=Marius|last=Zimand|publisher=Elsevier|year=2004|isbn=9780444828415|contribution=Theorem 2.4.3 (Compression theorem)|page=42|url=https://books.google.com/books?id=j-nhMYoZhgYC&pg=PA42}}.

Category:Computational complexity theory

Category:Structural complexity theory

Category:Theorems in the foundations of mathematics