Siguiente: Ejemplos Un nivel arriba: Complejidades condicionales Anterior: Complejidades condicionales

Teorema de Invarianza

Existe una función recursiva f₀ tal que para cualquier otra función recursiva f existe una constante c_f de manera que para cualesquiera dos objetos x,y se tiene

$$K_{f_0}(x\vert y)\leq K_f(x\vert y) + c_f.$$

• f₀ es un intérprete mínimo que se construye mediante una máquina universal.
• Dos funciones óptimas son equivalentes.

Así pues al fijar una máquina universal U₀ como máquina de referencia definimos:

• Complejidad condicional de x dado y: K(x|y)=K_f0(x|y).
• Complejidad incondicional de x: $K(x)=K(x\vert\mbox{\it nil})$.