imported>Jlwoodwa: Added {{No footnotes}} tag

2024-11-18T07:18:49Z

New page

{{No footnotes|date=November 2024}}
In [[computational complexity theory]], the '''compression theorem''' is an important theorem about the [[Computational complexity|complexity]] of [[computable function]]s.

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]] <math>\varphi</math> of the computable functions and a [[Blum complexity measure]] <math>\Phi</math> where a complexity class for a boundary function <math>f</math> is defined as
:<math>\mathrm{C}(f):= \{\varphi_i \in \mathbf{R}^{(1)} | (\forall^\infty x) \, \Phi_i (x) \leq f(x) \}.</math>

Then there exists a [[total computable function]] <math>f</math> so that for all <math>i</math>
:<math>\mathrm{Dom}(\varphi_i) = \mathrm{Dom}(\varphi_{f(i)})</math>
and
:<math>\mathrm{C}(\varphi_i) \subsetneq \mathrm{C}(\varphi_{f(i)}).</math>

==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}}.

{{DEFAULTSORT:Compression Theorem}}
[[Category:Computational complexity theory]]
[[Category:Structural complexity theory]]
[[Category:Theorems in the foundations of mathematics]]
{{Comp-sci-theory-stub}}

Compression theorem - Revision history

imported>Jlwoodwa: Added {{No footnotes}} tag