Siguiente: Conjuntos ralos Un nivel arriba: Estimaciones de la complejidad Anterior: Estimaciones de la complejidad

Kolmogorov

Sea $A\in N\times N$ recursivamente enumerable. Para cada $y\in N$ sea

$$M_y=\{x\vert(x,y)\in A\}=A^{-1}(y).$$

Entonces, salvo una constante que depende de A se tiene $\forall x,y$:

$$K(x\vert y)\leq \vert\mbox{\rm card}(M_y)\vert.$$