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 ninguna clase de complejidad máxima , con frontera computable, que contenga todas las funciones computables.

Dado un número de Gödel${\displaystyle \varphi }$de las funciones computables y una medida de complejidad de Blum${\displaystyle \Phi }$donde una clase de complejidad para una función de frontera${\displaystyle f}$se define como

${\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${\displaystyle f}$para que para todos${\displaystyle i}$

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

y

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

• Salomaa, Arto (1985), "Teorema 6.9", Computación y autómatas , Enciclopedia de matemáticas y sus aplicaciones, vol.  25, Cambridge University Press, pp. 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.