Compression theorem
≈ 1 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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== . .
Text derived from https://en.wikipedia.org/w/index.php?oldid=1258125946 under CC BY-SA 4.0; modifications have been made.