La teoría de la
complejidad computacional es la parte de la teoría de la computación que
estudia los recursos requeridos durante el cálculo para resolver un problema”.
Los recursos comúnmente estudiados son el tiempo (número de pasos de ejecución
de un algoritmo para resolver un problema) espacio (cantidad de memoria
utilizada para resolver un problema).
La teoría de la complejidad
computacional busca 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 basa en por qué tipo de problemas pueden ser
resueltos de manera algorítmica.
Historia
de la teoría de la complejidad computacional
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.
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.
El campo comenzó a
florecer cuando los investigadores Stephen Cook, norteamericano, Leonid
Levin, sovietico, trabajando de manera independiente, 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.
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. 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.
Problemas
y algoritmos
Un problema es una
pregunta a resolver por medio de un determinado algoritmo.
Problema
computacional: Un problema computacional constituye
una pregunta a ser respondida, teniendo generalmente varios parámetros, o
variables libres, cuyos valores no se han especificado. Un problema se describe
mediante: Una descripción general de todos sus parámetros y Una sentencia que
describa las propiedades que la respuesta debe cumplir.
Problema
de decisión: Un problema de decisión es un tipo
especial de problema computacional cuya respuesta es solamente "sí" o
"no". Los problemas de decisión constituyen uno de los principales
objetos de estudio de la teoría de la complejidad computacional, pues la
NP-completitud se aplica directamente a estos tipos de problemas en vez de a
problemas de optimización.
Algoritmos:
Los algoritmos son procedimientos paso-a-paso para resolver problemas. Se puede
pensar en ellos como simples programas de computadora, escritos en un lenguaje
artificial específico. Se dice que un algoritmo resuelve un problema A, si
dicho algoritmo se puede aplicar a cualquier instancia I de A, y se garantiza
que siempre produce una solución para dicha instancia.
Clases
de complejidad
Una clase de
complejidad es un conjunto de problemas que poseen la misma complejidad
computacional.
Las clases de
complejidad más sencillas se definen teniendo en cuenta factores como: El tipo
de problema computacional, El modelo de cómputo y El recurso (o recursos) que
está(n) siendo acotado(s) y la(s) cota(s).
Las principales clases
de complejidad computacional que existen son las siguientes: DTIME(f(n)), P, EXPTIME,
NTIME(f(n)), NP, NEXPTIME, DSPACE(f(n)), L, PSPACE, EXPSPACE, NSPACE(f(n)), NL,
NPSPACE, NEXPSPACE.
Problemas
tratables e intratables
Los problemas tratables
son aquellos que existe un algoritmo de tiempo polinómico (Clase de complejidad P) que lo resuelva.
Los problemas
intratables son aquellos que no existe un algoritmo conocido de tiempo
polinómico que lo resuelva.
Un algoritmo de
tiempo polinomial se define como aquel con función de complejidad temporal
en O(p(n)) para alguna función polinómica p, donde n denota
el tamaño de la entrada. Cualquier algoritmo cuya función de complejidad
temporal no pueda ser acotada de esta manera, se denomina algoritmo de
tiempo exponencial.
Máquina
de Turing
La máquina de Turing
(abreviado MT) tiene, un control finito, una cabeza lectora y una cinta
infinita donde puede haber caracteres, y donde eventualmente viene la palabra
de entrada. La cinta es de longitud infinita hacia la derecha, hacia donde se
extiende indefinidamente, llenándose los espacios con el carácter blanco.
La máquina de Turing comprende
la definición formal de lo que es un algoritmo. La máquina de Turing posee la
capacidad de resolver cualquier problema de las clases de complejidad
computacional.
Conclusión
La pregunta P=NP es una
de las más importantes en el campo de la teoría de la complejidad computacional,
debido a las grandes repercusiones que habría, en caso de encontrarse una
solución. Si P=NP, cualquier problema polinómicamente verificable sería
polinómicamente decidible. La mayoría de los investigadores cree que estas
clases no son iguales, porque se ha realizado bastantes esfuerzos, sin éxito,
para encontrar algoritmos de tiempo polinomial para varios problemas en NP.
