Teorema de compresión

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

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

Teorema de compresión

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

C()f):={}φ φ i▪ ▪ R()1)Silencio()О О JUEGO JUEGO x)CCPR CCPR i()x)≤ ≤ f()x)}.{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 f{displaystyle f} para siempre i{displaystyle i}

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

y

C()φ φ i)⊊ ⊊ C()φ φ f()i)).{displaystyle mathrm {C} (varphi _{i})subsetneq mathrm {C} (varphi _{f(i)}). }