In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
, the compression theorem is an important theorem about the
complexity
Complexity characterises the behaviour of a system or model whose components interaction, interact in multiple ways and follow local rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergence.
The term is generall ...
of
computable functions.
The theorem states that there exists no largest
complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of ...
, with computable boundary, which contains all computable functions.
Compression theorem
Given a
Gödel numbering
In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was developed by Kurt Gödel for the proof of his ...
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
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...
so that for all
:
and
:
References
*.
*.
Computational complexity theory
Structural complexity theory
Theorems in the foundations of mathematics
{{Comp-sci-theory-stub