Teoría de la Complejidad Computacional
La teoría de la complejidad computacional clasifica los problemas según la cantidad de tiempo, memoria y otros recursos que cualquier algoritmo necesita para resolverlos, estableciendo límites claros entre lo que es eficientemente resoluble y lo que parece intratable.
Definition
La teoría de la complejidad computacional estudia la dificultad intrínseca de los problemas computacionales medida por los recursos, principalmente el tiempo de ejecución y la memoria, requeridos para resolverlos en un modelo como la máquina de Turing, y agrupa los problemas en clases de complejidad en consecuencia.
Scope
Esta área abarca clases de complejidad de tiempo y espacio como P, NP, PSPACE y la jerarquía polinómica, la teoría de la NP-completitud y las reducciones de tiempo polinómico, la cuestión central de P versus NP, y modelos con recursos limitados que incorporan aleatoriedad, interacción y pruebas, junto con los resultados de jerarquía y dureza que relacionan estas clases.
Sub-topics
Core questions
- ¿Cuánto tiempo y memoria requiere inherentemente la resolución de un problema dado?
- ¿Qué problemas se pueden resolver eficientemente y cuáles parecen resistir todos los algoritmos eficientes?
- ¿Cómo se demuestra que los problemas son tan difíciles como los miembros más difíciles de una clase de complejidad?
- ¿La aleatoriedad, la interacción o el no determinismo añaden un poder computacional real?
Key theories
- Teoremas de jerarquía de tiempo y espacio
- Dado estrictamente más tiempo o espacio, las máquinas pueden resolver estrictamente más problemas, lo que demuestra que las clases de complejidad forman jerarquías genuinas y que algunos problemas son inherentemente más difíciles que otros.
- NP-completitud
- El teorema de Cook-Levin identifica problemas en NP a los que se reduce cualquier otro problema de NP, de modo que un único algoritmo eficiente para cualquiera de ellos los resolvería todos eficientemente.
- Modelos con recursos limitados
- La adición de aleatoriedad, interacción o alternancia define clases como BPP, IP y la jerarquía polinómica, cuyas relaciones precisan la imagen de lo que los recursos adicionales pueden y no pueden lograr.
Clinical relevance
La teoría de la complejidad guía la práctica al certificar qué problemas admiten algoritmos eficientes y cuáles son NP-difíciles y, por lo tanto, se abordan mejor con heurísticas o aproximaciones; la supuesta dificultad de ciertos problemas también sustenta la criptografía moderna, cuya seguridad se basa en tareas que se consideran computacionalmente inviables.
History
Hartmanis y Stearns fundaron el campo en 1965 al definir clases de complejidad y probar teoremas de jerarquía. Cook y Levin introdujeron la NP-completitud alrededor de 1971, Karp mostró muchos problemas naturales completos en 1972, y las décadas siguientes añadieron modelos de prueba aleatorizados, interactivos y verificables probabilísticamente.
Key figures
- Stephen Cook
- Richard Karp
- Leonid Levin
- Juris Hartmanis
Related topics
Seminal works
- cook1971
- hartmanisStearns1965
- aroraBarak2009
Frequently asked questions
- ¿Cuál es la diferencia entre computabilidad y complejidad?
- La computabilidad pregunta si un problema puede ser resuelto por algún algoritmo, ignorando el costo. La complejidad asume que el problema es resoluble y pregunta cuán costosa debe ser esa solución en tiempo y memoria, estableciendo distinciones más finas entre los problemas que son resolubles en principio.
- ¿Por qué es importante la NP-completitud en la práctica?
- Cuando se demuestra que un problema es NP-completo, se vincula a miles de otros para los que no se conoce ningún algoritmo eficiente a pesar de décadas de esfuerzo. Esto indica que buscar un algoritmo exacto rápido es probablemente inútil y que la aproximación, las heurísticas o los métodos de casos especiales son el camino realista.