¿Qué es la Complejidad Computacional?

Una aproximación a esta respuesta surge de la formulación misma de la pregunta.

Intuitivamente todos tenemos noción de la complejidad de hecho, usamos la palabra cotidianamente para significar situaciones difíciles de resolver. Trasladada la pregunta a un ámbito formal, matemático o de ingeniería podemos reformular la pregunta en la siguiente forma:

“¿Por qué algunos problemas son computacionalmente más difíciles que otros?”

Pues bien, la Teoría de la Complejidad tiene como finalidad dar respuesta a esta pregunta mediante la creación de herramientas que permitan describir un problema complejo mediante la definición de un posible o posibles algoritmos, si existen, que permitan solucionar un problema.

Hasta ahora podríamos decir que es una conclusión trivial, casi que evidente, pero ¿Por qué se llegó hasta aquí al punto de existir una teoría?

1. Un Poco de Historia.

Todo inicia con Alan Turing, un brillante matemático inglés, quien en 1936 desarrolló un modelo computacional teórico que años después probó estar en lo cierto a pesar de no haber considerado la cantidad de memoria y el tiempo de ejecución requeridos para un problema específico.

Hoy en día cualquier “gamer” sabe que la eficiencia de su sistema depende de la cantidad de memoria y el tiempo de respuesta, pero en la época de Turing, nos encontrábamos en los albores de la computación, no obstante, el modelo de Turing no pierde por ello su importancia y trascendencia.

1.1 La Máquina de Turing

La máquina de Turing se describe como un dispositivo que tiene k-cintas, cada cinta es una secuencia infinita de celdas cada una de las cuales contiene un símbolo de un alfabeto finito. Las cintas pueden ser leídas o escritas excepto la primera la cual solamente puede ser leída y se llama la cinta de entrada, las demás cintas se denominan cintas de trabajo siendo la última la cinta de salida o de resultados. Esta máquina hace sus cálculos en forma discreta, hacia adelante o atrás una celda cada vez.

Existe un número finito Q de estados almacenados en un registro donde cada estado corresponde a un solo símbolo, una vez leídos en cada paso, los estados se tiene la opción de hacer k-1 cambios.

El tiempo se contabilizaba como el número de pasos antes de detenerse y el espacio como el número de caracteres diferentes en las cintas.

Hoy en día podría decirse que la máquina de Turing se asimila a una computadora moderna: El registro podría ser la CPU y las cintas a la memoria; sin embargo, es muy útil pensar en que la máquina está orientada a resolver algoritmos (Escritos, por supuesto, en un lenguaje apropiado).

Y cuando se trata de resolver algoritmos hay que preguntarse que tan eficientemente se hace, es decir que recursos consume y cuánto tiempo se toma. Este análisis lo realizaron Hartmanis y Stearns en un conocido artículo publicado en 1965 denominado “On the Computational Complexity of Algorithms”, allí se establecen las definiciones de lo que sígnica la complejidad del tiempo y el espacio en la máquina de Turing y se demuestra que dado un mayor tiempo o espacio es posible hacer más cosas.

1.2 ¿Por qué la Maquina de Turing para abordar algoritmos?

Realmente es una cuestión de conveniencia, adaptación y resultados. La máquina como tal se definió para resolver algoritmos y si bien el concepto de algoritmo es algo intuitivo que podría relacionarse con “otras máquinas” es la de Touring la que ha demostrado que todos los algoritmos conocidos se pueden implementar en ella

Como síntesis de esta parte podemos decir que, con la idea de resolver algoritmos, llegamos a la máquina de Turing la cual confrontada en recursos y tiempo nos lleva a la teoría de la complejidad computacional.

2. Optimización y Decisión.

Dentro de la Teoría de la Complejidad Computacional, Existen problemas que comparten características similares y por ello pueden ser agrupados para su estudio.

· Problemas de optimización:

Son aquellos en los cuales se busca minimizar o maximizar el valor de una solución en un grupo de soluciones generadas para una entrada específica.

· Problemas de decisión:

Son aquellos donde se busca una respuesta de ‘’si’’ o ‘’no’’.

Cualquier problema de optimización puede ser manejado como un problema de decisión definiendo un valor objetivo y preguntando si existe o no una solución factible en el conjunto de soluciones con un valor de la solución máximo o mínimo según sea el caso. En ese sentido es más conveniente tratar con problemas de decisión que con problemas de optimización.

3. Clasificación de los Problemas de Decisión.

Los problemas de decisión pueden clasificarse desde dos puntos de vista:

3.1 Desde la Computabilidad, entendida esta como la parte de la lógica matemática que estudia los problemas que pueden ser resueltos con un algoritmo. Dicho esto, los problemas de decisión pueden ser:

o Decidibles o resolubles mediante algoritmos. Si existe un procedimiento, este se detiene ante cualquier entrada.

o Parcialmente Decidible o reconocible. Si existe un procedimiento este se detiene para las entradas que son solución.

o No decidible.

3.2 Desde la Complejidad Computacional se definen varias clases de decisiones. Antes de describirlas conviene aclarar algunos términos:

· Tiempo Polinómico: En 1965, Edmonds definió un algoritmo en el cual un polinomio limitaba el tiempo de ejecución; por eso la denominación.

· Máquina de Turing (MT) Determinista y no determinista: La entrada de una máquina de Turing viene determinada por una pareja: estado actual y símbolo leído. Las acciones por tomar en función de la entrada son el cambio de estado, la escritura de un nuevo símbolo y el movimiento del dispositivo hacia adelante o hacia atrás. En el caso de que exista a lo sumo una posibilidad de ejecución para cada pareja, se dirá que es MT determinista, mientras que en el caso de que exista al menos una pareja con más de una posible combinación de actuaciones se dirá que se trata de una MT no determinista.

· Reducción: Reducir en este contexto es una forma de convertir un problema en otro tal que la solución de este último sirva para resolver el primero.

Las clases de problemas de decisión son entonces:

o Clase L (D Log Space): Son aquellos problemas que pueden ser resueltos por una MT determinista utilizando una cantidad de espacio o memoria logarítmicamente proporcional al tamaño de la entrada: log(n), donde n es el tamaño de la entrada; en estos problemas si existe una solución es única.

o Clase NL (Nondeterministic Logarithmic space): Son los problemas de decisión que pueden ser resueltos en espacio log(n), por una MT no determinista tal que la solución si existe es única.

o Clase P (Polynomial Time): Son todos aquellos problemas de decisión que pueden ser resueltos por una MT determinista en un período de tiempo polinómico. Estos problemas son tratables, es decir se pueden resolver en tiempos razonable; buena parte de los problemas de ordenamiento, priorización y búsqueda caben dentro de esta clase.

o Clase NP (Non Deterministic Polynomial Time): Formalmente, es el conjunto de problemas que pueden ser resueltos en tiempo polinómico por una MT no determinista. Una definición más intuitiva es la siguiente: Es el conjunto de los problemas de decisión para los cuales las instancias donde la respuesta es “si” tienen demostraciones verificables por cálculos determinísticos en tiempo polinómico.

La importancia de esta clase de problemas es que es aplicable cuando se desea saber si existe una cierta solución o si existe una mejor solución que las conocidas.

o Clase NP-Completo: Estos problemas son NP, sus soluciones sus soluciones son reducibles a NP en tiempo polinómico.

o Clase NP-Hard: Informalmente son aquellos problemas tan difíciles de resolver como el más difícil de NP.

Nadie, hasta ahora, ha podido demostrar en forma concluyente que todos los problemas NP-Completos se pueden resolver dentro de tiempos polinomiales, esto ha creado una de las grandes discusiones científicas al punto que el Instituto Clay de Matemáticas definió este como como uno de los siete problemas insolubles y ofrece para quien lo demuestre una recompensa de US 1.000.000.

Stephen Cook y Leonid Levin formularon en 1971 la pregunta en la siguiente forma donde P (Entendido como fácil de encontrar) y NP (Entendido como fácil de probar) se relacionan así:

¿Es P=NP o es P≠NP?

Coloquialmente: ¿Es posible “verificar” rápidamente soluciones positivas a un problema de decisión? y si así fuera: ¿Se pueden “obtener” las respuestas rápidamente?

Esta pregunta y su eventual respuesta son el fundamento de la Complejidad Computacional.