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 of the computable functions and a Blum complexity measure
where a complexity class for a boundary function
is defined as
Then there exists a total computable function so that for all
and
References
- Salomaa, Arto (1985), "Theorem 6.9", Computation and Automata, Encyclopedia of Mathematics and Its Applications 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 196, Elsevier, p. 42, ISBN 9780444828415.