Clases de Complejidad de Tiempo y Espacio

Las clases de complejidad agrupan problemas de decisión según el tiempo o la memoria que una máquina necesita para resolverlos, organizando la computación en un paisaje estructurado desde el espacio logarítmico hasta el tiempo exponencial.

Definition

Una clase de complejidad es el conjunto de problemas resolubles dentro de un límite establecido en un recurso, típicamente el tiempo o la memoria de trabajo utilizada por una máquina de Turing en función de la longitud de la entrada, con variantes deterministas y no deterministas para cada recurso.

Scope

Este tema abarca la definición de clases de tiempo y espacio deterministas y no deterministas como P, NP, L, NL, PSPACE y EXPTIME, los teoremas de jerarquía que las separan, las inclusiones y relaciones conocidas entre ellas, el teorema de Savitch que relaciona el espacio no determinista y determinista, y los problemas completos que caracterizan cada clase.

Core questions

• ¿Cómo se agrupan los problemas según el tiempo y la memoria que requiere su solución?
• ¿Qué inclusiones entre las clases de complejidad estándar se sabe que son estrictas?
• ¿Cómo se relaciona el espacio no determinista con el espacio determinista?
• ¿Qué papel juegan los problemas completos en la caracterización de una clase?

Key theories

Teoremas de jerarquía

Con asintóticamente más tiempo o espacio, una máquina puede decidir estrictamente más lenguajes, por lo que las clases de tiempo y espacio forman jerarquías adecuadas y los recursos no pueden desperdiciarse sin perder problemas.

Teorema de Savitch

Cualquier problema resoluble en espacio no determinista puede resolverse de forma determinista utilizando solo el cuadrado de ese espacio, por lo que para la memoria, a diferencia de lo que aparentemente ocurre con el tiempo, el no determinismo proporciona como máximo una ventaja modesta.

Clinical relevance

Ubicar un problema en una clase de complejidad indica a los profesionales qué esperar: los problemas en P se escalan a entradas grandes, los problemas PSPACE-completos, como muchos juegos y tareas de planificación, resisten una solución eficiente, y la estructura de la clase guía si se deben buscar algoritmos exactos, aproximaciones o rediseñar el problema.

History

Hartmanis y Stearns definieron las clases con límite de tiempo y probaron el teorema de la jerarquía de tiempo en 1965, fundando el campo. La complejidad del espacio se desarrolló en paralelo, con el teorema de Savitch de 1970 y resultados posteriores como el cierre del espacio no determinista bajo complemento de Immerman y Szelepcsényi, que refinaron el panorama.

Key figures

• Juris Hartmanis
• Richard Stearns
• Walter Savitch
• Stephen Cook

Seminal works

• hartmanisStearns1965
• savitch1970

Frequently asked questions

¿Cuál es la diferencia entre la complejidad de tiempo y la de espacio?

La complejidad de tiempo cuenta el número de pasos que toma un algoritmo, mientras que la complejidad de espacio mide la memoria de trabajo que utiliza. Se comportan de manera diferente: el espacio puede reutilizarse a medida que avanza una computación, razón por la cual el espacio no determinista es mucho menos potente en relación con el espacio determinista de lo que parece ser la comparación análoga para el tiempo.

¿Por qué son importantes los teoremas de jerarquía?

Demuestran que más recursos permiten genuinamente resolver más problemas, descartando la posibilidad de que todas las clases colapsen en una sola. Esto garantiza, por ejemplo, que existen problemas resolubles en tiempo exponencial pero no en tiempo polinómico, lo que ancla todo el edificio de las clases de complejidad.