teoría de la complejidad

La Teoría de la Complejidad Computacional es una rama de la teoría de la computación que se centra en la clasificación de los problemas computacionales de acuerdo a su dificultad inherente, y en la relación entre dichas clases de complejidad.
Un problema se cataloga como "inherentemente difícil" si su solución requiere de una cantidad significativa de recursos computacionales, sin importar elalgoritmo utilizado. La teoría de la complejidad computacional formaliza dicha aseveración, introduciendo modelos de cómputo matemáticos para el estudio de estos problemas y la cuantificación de la cantidad de recursos necesarios para resolverlos, como tiempo y memoria.
Uno de los roles de la teoría de la complejidad computacional es determinar los límites prácticos de qué es lo que se puede haceren una computadora y qué no. Otros campos relacionados con la teoría de la complejidad computacional son el análisis de algoritmos y la teoría de la computabilidad. Una diferencia significativa entre el análisis de algoritmos y la teoría de la complejidad computacional, es que el primero se dedica a determinar la cantidad de recursos requeridos por un algoritmo en particular para resolver unproblema, mientras que la segunda, analiza todos los posibles algoritmos que pudieran ser usados para resolver el mismo problema.
La teoría de la complejidad computacional trata de clasificar los problemas que pueden, o no pueden ser resueltos con una cantidad determinada de recursos. A su vez, la imposición de restricciones sobre estos recursos, es lo que la distingue de la teoría de lacomputabilidad, la cual se preocupa por qué tipo de problemas pueden ser resueltos de manera algorítmica.
Índice [ocultar]
1 Historia
2 Problemas, algoritmos y complejidad
2.1 Problema computacional
2.2 Problemas de decisión
2.3 Algoritmos
2.4 Algoritmos de tiempo polinómico y problemas intratables
3 Clases de complejidad
3.1 Definiendo clases de complejidad
3.2 Máquinas de Turing deterministas yla clase P
3.3 Computación no determinista y la clase NP
3.4 Clases de complejidad importantes
4 La pregunta P=NP
5 NP-Completitud
5.1 Reducción polinomial
5.2 Problemas NP-completos
5.3 Importancia de la NP-Completitud
6 Haciendo frente a problemas NP
7 Véase también
8 Referencias
8.1 Artículos
8.2 Libros de texto
Historia [editar · editar código]

Antes de que se realizaraninvestigaciones en torno a la complejidad de los algoritmos, se crearon los cimientos de esta teoría por varios investigadores. Uno de los aportes más influyentes fue la definición de las Máquinas de Turing en 1936, las cuales resultaron ser una noción de computadora muy flexible y robusta. A medida que las computadoras se desarrollaban en los 40's y los 50's, la Máquina de Turing demostró ser el modeloteórico correcto de cómputo.
Sin embargo, rápidamente se descubrió que el modelo básico de la Máquina de Turing fallaba al cuantificar el tiempo y la memoria requerida por una computadora, un problema crítico hoy en día, y aún más en aquellos tiempos. La idea de medir el tiempo y espacio como una función de la longitud de la entrada, se originó a principios de los 60's por Hartmanis and Stearns,y así, nació la teoría de la complejidad computacional.
En los inicios, los investigadores trataban de entender las nuevas medidas de complejidad, y cómo se relacionaban unas con otras. En 1965, Edmonds definió un "buen" algoritmo como uno con un tiempo de ejecución acotado por un polinomio, es decir, con un tiempo de ejecución polinómico.1 Esto condujo al surgimiento de uno de los conceptos másimportantes de la teoría de la complejidad computacional: la NP-completitud y su pregunta fundamental, si P=NP.
El campo comenzó a florecer cuando el investigador norteamericano Stephen Cook, trabajando de manera independiente al investigador soviético Leonid Levin, probaron que existen problemas relevantes que son NP-completos. En 1972, Richard Karp llevó esta idea un paso más adelante,...