Teoría de la complejidad computacional

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 el algoritmo 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 fines de la teoría de la complejidad computacional es determinar los límites prácticos de qué es lo que se puede hacer en 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 un problema, 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 la computabilidad, la cual se preocupa por qué tipo de problemas pueden ser resueltos de manera algorítmica.

Historia

Antes de que se realizaran investigaciones 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 modelo teó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ás importantes 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, demostrando que 21 problemas combinatorios y de teoría de grafos, caracterizados por ser computacionalmente intratables, eran NP-completos.[2] También en los 70's, se produjo un crecimiento de las clases de complejidad a medida que los investigadores trataban de comprender los distintos modelos de cómputo existentes.

En los 80's, se produjo un auge de los modelos finitos, que analizaban el proceso de cómputo de una manera inherentemente distinta. Surgió un nuevo acercamiento a problemas como P=NP, y aún cuando estos modelos tenían sus limitaciones separando las clases de complejidad, esta aproximación introdujo técnicas combinatorias que permitieron un mejor entendimiento de los límites de estos modelos.

Ya en los 90's, se estudiaron nuevos modelos de cómputo como las computadoras cuánticas, donde una misma tarea puede tener diferente complejidad en la computación clásica y en la computación cuántica. Sin embargo, existen varias limitantes, entre ellas, la de desarrollar un hardware para este modelo, y que se requieren grandes cantidades de espacio para realizar los cálculos.

Other Languages
norsk bokmål: Kompleksitetsteori
srpskohrvatski / српскохрватски: Računska teorija složenosti
slovenčina: Teória zložitosti