Teorema de compresión

En la teoría de la complejidad computacional , el teorema de compresión es un teorema importante sobre la complejidad de las funciones computables .

El teorema establece que no existe una clase de complejidad máxima , con límite computable, que contenga todas las funciones computables.

Teorema de compresión

Dada una numeración de Gödel de las funciones computables y una medida de complejidad de Blum donde una clase de complejidad para una función límite se define como ${\displaystyle \varphi }$ ${\displaystyle \Phi }$ ${\displaystyle f}$

${\displaystyle \mathrm {C} (f):=\{\varphi _{i}\in \mathbf {R} ^{(1)}|(\forall ^{\infty }x)\,\Phi _{i}(x)\leq f(x)\}.}$

Entonces existe una función computable total tal que para todos ${\displaystyle f}$ ${\displaystyle i}$

${\displaystyle \mathrm {Dom} (\varphi _{i})=\mathrm {Dom} (\varphi _{f(i)})}$

y

${\displaystyle \mathrm {C} (\varphi _{i})\subsetneq \mathrm {C} (\varphi _{f(i)}).}$

Referencias

• Salomaa, Arto (1985), "Teorema 6.9", Computación y autómatas, Enciclopedia de matemáticas y sus aplicaciones, vol. 25, Cambridge University Press, págs. 149-150, ISBN 9780521302456.
• Zimand, Marius (2004), "Teorema 2.4.3 (Teorema de compresión)", Complejidad computacional: una perspectiva cuantitativa, North-Holland Mathematics Studies, vol. 196, Elsevier, pág. 42, ISBN 9780444828415.