Siguiente: Incomprimibilidad Un nivel arriba: Complejidades condicionales Anterior: Teorema de Invarianza

Ejemplos

1. $K(xx)\leq K(x)+O(1)$.


2. Sea $<\cdot>:D\times D\rightarrow D$ una función de apareamiento. Para una pareja $(x,y)\in D^2$ definamos

K(x,y)=K(<x,y>).

Como es necesario mantener un registro de las longitudes de x y de y tendremos

$$K(x,y)\leq K(x)+K(y)+O(\log(\mathop{\rm Min}\{K(x),K(y)\})).$$