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

Propiedades

Para las cadenas x se cumple:


1. $K(x)\leq \vert x\vert$, salvo una constante independiente de x.


2. La relación anterior se cumple para la mayoría de las palabras:

$$\\ frac{\mbox{\rm card}\{x:K(x)<\vert x\vert-m\}}{2^m}\leq 2^{-m}.$$

3. $\lim_{\vert x\vert\rightarrow\infty}K(x)=\infty.$


4. Más aún: Si $m(x)=\mathop{\rm Min}\{K(y)\vert y\geq x\}$ entonces $\lim_{\vert x\vert\rightarrow\infty}m(x)=\infty.$


5. La función m(x) queda a la larga dominada por una función recursiva monótona creciente.


6. K es ``uniformemente contínua'':

$$\vert K(x+h)-K(x)\vert\leq 2\vert h\vert.$$