Compression theorem
Encyclopedia
In computational complexity theory
the compression theorem is an important theorem about the complexity of computable function
s.
The theorem states that there exists no largest complexity class
, with computable boundary, which contains all computable function
s.
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
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
the compression theorem is an important theorem about the complexity of computable function
Computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
s.
The theorem states that there exists no largest complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
, with computable boundary, which contains all computable function
Computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
s.
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 asThen there exists a total computable function
so that for all and