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 roles 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.

       La Complejidad computacional estudia el problema, considerando globalmente todos los algoritmos posibles para resolverlo (<incluso los que no conocemos!) Ejemplo: cuál es la mejor complejidad temporal que podemos conseguir para ordenar un array de tamaño n?

         Sabemos que podemos hacerlo en O (nlog (n)); pero podemos hacerlo mas rápido?

       Si la respuesta es "si", podemos demostrarlo encontrando un algoritmo mas rápido. Pero si es "no", buscar algoritmos mejores será perder el tiempo. Necesitamos razonar sobre el problema en su conjunto, mas allá de algoritmos concretos!

CLASES DE COMPLEJIDAD

     Una clase de complejidad es un conjunto de problemas que poseen la misma complejidad computacional.

Definiendo clases de complejidad:

         Las clases de complejidad más sencillas se definen teniendo en cuenta factores como:

• El tipo de problema computacional: Los problemas más comúnmente utilizados son los problemas de decisión, pero las clases de complejidad se pueden definir para otros tipos de problemas.

• El modelo de cómputo: El modelo de cómputo más común es la Máquina de Turing determinista, pero muchas clases de complejidad se basan en Máquinas de Turing no deterministas, Máquinas de Turing cuánticas, etc.

• El recurso (o recursos) que está(n) siendo acotado(s) y la(s) cota(s): Estas dos propiedades usualmente se utilizan juntas, por ejemplo, "tiempo polinomial", "espacio logarítmico", "profundidad constante", etc.

MÁQUINAS DE TURING DETERMINISTAS Y LA CLASE P

       La clase P contiene a aquellos problemas que son solubles en tiempo polinómico por una máquina de Turing determinista.

       Para la definición anterior se ha fijado el modelo de cómputo: la Máquina de Turing determinista. Existen distintas variantes de la Máquina de Turing y es conocido que la más débil de ellas puede simular a la más fuerte, adicionando a lo sumo un tiempo polinómico. En las décadas posteriores a la Tesis de Church-Turing surgieron otros modelos de cómputo, y se pudo mostrar que la Máquina de Turing también podía simularlos a lo sumo adicionando también un tiempo polinómico. Por tanto, la clase análoga a P para dichos modelos no es mayor que la clase P para el modelo de cómputo de la máquina de Turing.

          La clase P juega un papel importante en la teoría de la complejidad computacional debido a que:

1. P es invariante para todos los modelos de cómputo que son polinómicamente equivalentes a la Máquina de Turing determinista.

2. A grandes rasgos, P corresponde a la clase de problemas que, de manera realista, son solubles en una computadora.

COMPUTACIÓN NO DETERMINISTA Y LA CLASE NP

       Muchas veces podemos evitar utilizar la fuerza bruta en los problemas para obtener soluciones en tiempo polinómico. Sin embargo, para algunos problemas esto no ha podido lograrse, es decir, no se conocen algoritmos que los resuelvan en tiempo polinómico. Quizás estos problemas tengan algoritmos en tiempo polinomial que se basan en principios por ahora desconocidos, o quizás estos problemas no pueden ser resueltos en tiempo polinómico, debido a que son "inherentemente difíciles".

      La clase de complejidad NP consta de los problemas "verificables" en tiempo polinómico. Por verificable se entiende a un problema tal que dado un certificado de solución (candidato a solución), se puede verificar que dicho certificado es correcto en un tiempo polinómico en el tamaño de la entrada. A los problemas en la clase NP usualmente se les llama problemas NP.6

       El término NP proviene de no determinista en tiempo polinómico y se deriva de un caracterización alternativa de esta clase, donde se utilizan Máquinas de Turing no deterministas. Informalmente, se puede definir la clase NP en términos de un algoritmo no determinista (recordar la equivalencia entre algoritmo y Máquina de Turing).

        El algoritmo mencionado está compuesto por 2 etapas separadas. Dada una instancia del problema I, la primera etapa simplemente "adivina" un candidato a solución S. Entonces, la etapa de verificación recibe como entrada a I y a S, y procede a realizar el cómputo de una manera determinista, finalmente deteniéndose con la respuesta "sí", o con la respuesta "no", o sigue computando sin detenerse.

        Al igual que la clase P, la clase NP es insensible a la elección del modelo de cómputo no determinista, debido a que dichos modelos son equivalentes polinómicamente.

IMPORTANCIA DE LA NP-COMPLETITUD

        Quizás la razón de mayor peso por la cual los científicos de la computación creen que P es distinto de NP, es la existencia de la clase de problemas "NP-completos". Esta clase tiene la curiosa propiedad de que si algún problema NP-completo puede ser resuelto en tiempo polinomial, entonces todo problema en NP tiene una solución en tiempo polinomial, es decir, P=NP. A pesar de años de estudio, ningún algoritmo de tiempo polinomial se ha descubierto para ningún problema NP-completo.

         Desde el punto de vista teórico, un investigador intentando mostrar que la clase P es distinta de la clase NP, pudiera enfocarse en un problema NP-completo. Si algún problema en NP requiere más que un tiempo polinomial, entonces uno NP-completo también. Además, un investigador intentando demostrar que P=NP, solo necesita encontrar un algoritmo de tiempo polinomial para un problema NP-completo para lograrlo.

        Desde el punto de vista práctico, el fenómeno de la NP-completitud puede prevenir la pérdida de tiempo cuando se busca un algoritmo de tiempo polinomial no existente para resolver un problema determinado. Aún cuando no se posean los elementos matemáticos para demostrar que cierto problema no se puede resolver en tiempo polinomial, creemos que P no es igual a NP, así que demostrar que el problema es NP-completo, es una fuerte evidencia de su no "polinomialidad".

COMPLEJIDAD DE LOS PROBLEMAS

         La clasificación de la complejidad de los problemas es en cuatro clases [Flores de la Mota, 2002]: 

Problemas Indecidibles: Son problemas para los cuales no se puede escribir un algoritmo para su solución, por lo tanto son los problemas de complejidad más alta. 

Problemas Intratables: Son los problemas para los cuales no se puede desarrollar un algoritmo de tiempo polinomial, únicamente algoritmos exponenciales. 

Problemas NP (Polinomial no determinístico): Son los problemas para los cuales la factibilidad del problema utilizando el correspondiente problema de decisión, puede ser verificada en tiempo polinomial, sin embargo, el problema solo puede resolverse con algoritmos no determinísticos. 

       Un algoritmo no determinístico es un modelo teórico de computación donde la computadora debe adivinar que paso seguir, y en caso de existir un conjunto de adivinanzas que la computadora debiera resolver, entonces se supone que adivina correctamente. Obviamente este tipo de modelo es imposible de implementar. 

Problemas P: Si un problema está en la clase P, se dice que es polinomial y significa que existe un algoritmo de tiempo polinomial para su solución. 

La teorıa de NP-completitud:

         Se aplica a problemas de decisión, o sea problemas que tienen como respuesta SI o NO (aunque es sencillo ver que sus implicancias pueden extenderse a problemas de optimizacion). En el caso del problema de TSP, la variante de decisión se podría formular como: “¿existe un circuito Hamiltoniano de longitud menor o igual a k?” Un problema de decisión consiste entonces de un conjunto de instancias y un subconjunto de instancias cuya respuesta es SI.