Siguiente: Ordenes de funciones Un nivel arriba: COMPUTABILIDAD Y COMPLEJIDAD Anterior: Enumerabilidad recursiva relativa a

Teoremas de jerarquía

Presentaremos en este capítulo los fundamentos de las jerarquías espacial y temporal de la clase de los problemas tratables computacionalmente. Inicialmente presentamos los conceptos de órdenes de crecimiento de funciones reales, pues en términos de ellos nos referiremos a las complejidades de los problemas tratables. Veremos que en la clase de esos problemas no hay problemas ``más difíciles'' en el sentido de que dado cualquiera, siempre se puede tener un problema más difícil que ése. Veremos algunas condiciones suficientes para distinguir niveles de complejidad en las jerarquías deterministas espacial y temporal, compararemos algunos niveles de ellas y posteriormente veremos propiedades de las jerarquías no-deterministas. Finalmente, con el teorema de Borodin veremos que se puede tener dos funciones muy diversas que determinan, sin embargo, un mismo nivel en la jerarquía determinista espacial.