Siguiente: Teorema de Invarianza Un nivel arriba: Presentación de la teoría Anterior: Observaciones

Complejidades condicionales

Un intérprete en D es una función

$$\begin{eqnarray*}f:\{0,1\}^{<\omega}\times D &\rightarrow& D \\ (p,y) &\mapsto& f(p,y)=x \end{eqnarray*}$$

Para cada $x\in D$ su complejidad condicional, dada y según f, es

$$K_f(x\vert y)=\left\{\begin{array}{ll} \mathop{\rm Min}\{\ve... ...$p$,} \\ \infty &\mbox{\rm en otro caso.} \end{array}\right.$$