Llegamos a la última parte de esto que dí en llamar “Introducción a los Algoritmos“. Y aunque sé que pareció mucho, sólo ha sido rasgar la trama superficial.
La complejidad computacional considera globalmente todos los posibles algoritmos para resolver un problema dado.
Estamos interesados en la distinción que existe entre los problemas que pueden ser resueltos por un algoritmo en tiempo polinómico y los problemas para los cuales no conocemos ningún algoritmo polinómico, es decir, el mejor es no–polinómico.
La teoría de la NP–Completitud no proporciona un método para obtener algoritmos de tiempo polinómico, ni dice que que estos algoritmos no existan. Lo que muestra es que muchos de los problemas para los cuales no conocemos algoritmos polinómicos están computacionalmente relacionados.
Algoritmos y Complejidad
En los capítulos anteriores, hemos visto que los algoritmos cuya complejidad es descrita por una función polinomial pueden ser ejecutados para entradas grandes en una cantidad de tiempo razonable, mientras que los algoritmos exponenciales son de poca utilidad excepto para entradas pequeñas.
En esta sección se tratarán los problemas cuya complejidad es descrita por funciones exponenciales, problemas para los cuales el mejor algoritmo conocido requeriría de muchos años o centurias de tiempo de cálculo para entradas moderadamente grandes.
De esta forma se presentarán definiciones que pretenden distinguir entre los problemas tratables (aquellos que no son tan duros) y los problemas intratables (duros o que consumen mucho tiempo). La mayoría de estos problemas ocurren como problemas de optimización combinatoria.
Problemas NP Completos
Definición Formal de la Clase NP
La definición formal de NP–completo usa reducciones, o transformaciones, de un problema a otro.
Una definición formal de NP-completo es:
Un problema P es NP-completo si éste está en NP y para cada otro problema P ’ en NP, P ’ µ P
Del teorema anterior y la definición de NP completo se deduce el siguiente teorema:
Si cualquier problema NP-completo esta en P, entonces P=NP
Este teorema indica, por un lado, que tan valioso sería encontrar un algoritmo polinomialmente acotado para cualquier problema NP-completo y, por otro, que tan improbable es que tal algoritmo exista pues hay muchos problemas en NP para los cuales han sido buscados algoritmos polinomialmente acotados sin ningún éxito.
Como se señaló antes, el primer problema de decisión que se propuso como un problema NP-completo es el satisfactibilidad de la lógica proposicional. Todos los problemas NP para los cuales se puede comprobar que pueden ser reducibles al problema de satisfctibilidad, son NPcompletos.
Así tenemos que los siguientes problemas son NP-completos: rutas y circuitos de Hamilton, asignación de trabajos con penalizaciones, el agente viajero, el problema de la mochila.
Actualmente para probar que un problema es NP-completo, es suficiente con probar que algún otro problema NP-completo es polinomialmente reducible a éste debido a que la relación de reducibilidad es transitiva. La lógica de lo dicho es la siguiente:
- Si P’ es NP-completo, entonces todos los problemas en NP µ P’
- Si se demuestra que P’ µ P
- Entonces todos los problemas en NP µ P
- Por lo tanto, P es NP-completo
Supóngase un problema P, P* es el complemento del problema P si el conjunto de símbolos en la cadena s de la fase de adivinación del algoritmo no determinístico que codifican las instancias si de P* son exactamente aquellas que no están codificando las instancias si de P.
Por ejemplo, el problema del circuito Hamiltoniano es: dado un grafo G=(V, E), es G Hamiltoniano. Y el complemento del problema del circuito Hamiltoniano es: dado un grafo G=(V, E), es G no Hamiltoniano.
Supóngase un problema P en P, entonces hay un algoritmo acotado polinomialmente que resuelve P. Un algoritmo acotado polinomialmente que solucione el complemento de P es exactamente el mismo algoritmo, únicamente con la sustitución de no por si cuando se obtiene una solución afirmativa y viceversa. El siguiente teorema expresa lo mencionado
Si P es un problema en P, entonces el complemento P * de P está también en P.
Los mismos argumentos no pueden ser aplicados para demostrar que un problema en NP está también en NP. Esto motiva la siguiente definición: La clase co. NP es la clase de todos los problemas que son complemento de problemas en NP.
Decir que el complemento de todos los problemas en NP está también en NP es equivalente a decir que NP = co-NP. Sin embargo, hay razones para creer que NP¹ co-NP. La evidencia es tan circunstancial como la que se estableció para la conjetura de que P¹ NP: Muchos investigadores han tratado por largo tiempo, sin éxito, de construir pruebas sucintas para el complemento del problema del circuito Hamiltoniano, así como para muchos otros problemas. Sin embargo, puede ser mostrado (como con P¹ NP) que si la conjetura es verdadera, está en los problemas NP-completo testificar su validez.
Si el complemento de un problema NP-completo está en NP, entonces NP = co-NP. Así de todos los problemas en NP, Los problemas NP-completo son aquellos con complementos de estar en NP. Contrariamente, si el complemento de un problema en NP está también en NP, esto es evidencia de que el problema no está en NP.
Cuando todos los problemas en NP se transforman polinomialmente al problema P, pero no es posible demostrar P Í NP, se dice que P es tan difícil como cualquier problema en NP y por lo tanto NP–hard.
NP-hard es usado también en la literatura para referirse a los problemas de optimización de los cuales su problema de decisión asociado es NP-completo Problemas que pueden ser solucionados por algoritmos cuyas operaciones pueden ser confinadas dentro de una cantidad de espacio que está acotado por un polinomio del tamaño de la entrada, pertenecen a la clase PSPACE.
P, NP y co-NP son subconjuntos de PSPACE. Se dice que un problema es PSPACE-completo si éste está en PSPACE y
todos los otros problemas en PSPACE son polinomialmente reducibles a él.
Problemas Intratables
Garey & Johnson, plantean una situación de intratabilidad interesante que describimos a través del siguiente caso: Si trabajas para una compañía que está pensando entrar a una nueva era globalizadora de gobierno y tu jefe te propone que obtengas un método para determinar si o no cualquier conjunto dado de especificaciones para un nuevo componente pueden ser satisfechas de alguna manera y, si es así, se deberá construir el diseño que satisfaga dichas expecificaciones. La realidad es que después de un tiempo comprobarás que no hay manera de obtener tal método. De modo que tendrás dos alternativas:
- Renunciar para evitar la pena de que te corran por inepto.
- Esperar a que te corran por inepto. Sería muy penoso, pero tendrías que confesar que no pudiste resolver el problema por falta de capacidad.
Para evitar la situación anterior tú podrías tratar de tomar una actitud de una persona más valiente y demostrar que en realidad dicho método no se puede obtener. Si eso fuera así entonces tú podrías ir con tu jefe y aclararle que el problema no lo resolviste porque no se puede resolver: Es intratable.
Sin embargo, es muy probable que a tu jefe esta característica del problema le tenga sin cuidado y, de todas maneras, te corran o tengas que renunciar. Es decir regresarás a las alternativas: 1 y 2 antes citadas.
Una situación más prometedora, es tratar de probar que el problema no solo es tan difícil que no se puede resolver, sino que además pertenece a una clase de problemas tales que cientos y miles de personas famosas e inteligentes, tampoco pudieron resolver. Aún así, no estamos muy seguros aún de tu permanencia en la compañía!.
En realidad el conocimiento de que un problema es intratable es de gran utilidad en problemas de tipo computacional. Dado que el problema completo es intratable, tu podrías resolver el problema para ciertas instancias del mismo, o bien, resolver un problema menos ambicioso. Por ejemplo, podrá conformarte con obtener un método para las especificaciones de solo cierto tipo de componentes para determinados conjuntos de entrada y no para “cualquier conjunto dado de especificaciones”. Esto seguramente
te llevará a tener mejor relaciones con tu compañía.
En general, nos interesa encontrar el algoritmo más eficiente para resolver un problema determinado. Desde ese punto de vista tendríamos que considerar todos los recursos utilizados de manera que el algoritmo más eficiente sería aquél que consumiera menos recursos. ¿Cuáles recursos? Si pensamos nuevamente que tu jefe te encarga que obtengas el algoritmo más
eficiente, es decir el que consume menos recursos so pena de que si no lo obtienes seas eliminado de la nomina de la compañía, estoy seguro, en que pensarías en todos los recursos posibles (horas-hombre para construir el algoritmo, tiempo de sintonización, tiempo requerido para obtener una solución, número de procesadores empleados, cantidad de memoria requerida, etc.). Para simplificar un poco la tarea, consideraremos que tu jefe te permite que la eficiencia la midas sobre un solo recurso: El tiempo de
ejecución. Pensemos por un momento que solo se tiene una sola máquina de modo que el número de procesadores no requiere de un análisis. ¿Qué le pasó a tu jefe? ¿De pronto se volvió comprensivo contigo? En realidad los otros parámetros los ha tomado en cuenta como costo directo del programa en cuestión. Esto es en realidad lo que se hace en teoría de complejidad. Para el análisis de complejidad, se considera por lo general la eficiencia sobre el tiempo, para un solo procesador en cómputo secuencial; para cómputo paralelo se considera también el número de procesadores.
Los algorimos han sido divididos como buenos o malos algoritmos. La comunidad computacional acepta que un buen algoritmo es aquél para el cual existe un algoritmo polinomial determinístico que lo resuelva. También se acepta que un mal algoritmo es aquel para el cual dicho algoritmo simplemente no existe. Un problema se dice intratable, si es muy difícil que un algoritmo de tiempo no polinomial lo resuelva. No obstante, esta clasificación de algoritmos en buenos y malos puede resultar a veces engañosa, ya que se podría pensar que los algoritmos exponenciales no son de utilidad práctica y que habrá que utilizar solamente algoritmos polinomiales. Sin embargo se tiene el caso de los métodos simplex y Branch and Bound, los cuales son muy eficientes para muchos problemas prácticos.
Desafortunadamente ejemplos como estos dos son raros, de modo que es preferible seguir empleando como regla de clasificación en buenos y malos algoritmos, la que lo hace dependiendo de si son o no polinomiales; todo esto con la prudencia necesaria.
La teoría de la NP-Completés fué presentada inicialmente por Cook desde 1971. Cook probó que un problema particular que se estudia en Lógica (no necesitamos ahora estudiarlo) y que se llama “El Problema de Satisfactibilidad“, tenía la propiedad de que cualquier problema que perteneciera a la clase NP, podía ser reducido a él a través de una transformación de tipo polinomial. Esto significaba que si el problema de satisfactibilidad podía ser resuelto en tiempo polinomial, todos los problemas No Polinomiales también podrían resolverse en tiempo polinomial, lo que significaría que la clase NP dejaría de existir!!.
De esta forma, si cualquier problema en NP es intratable, entonces satisfactibilidad es un problema intratable. Cook también sugirió que el problema de satisfactibilidad y otros problemas NP tenían la característica de ser los problemas más duros. Estos problemas tienen dos versiones: de decisión y de optimización. El conjunto de estos problemas de optimización se denominan NP Completos, mientras que a sus correspondientes problemas de optimización, reciben el nombre de NP Hard.
Problemas de Decisión
Aquí hemos hablado de problemas de optimización como aquél donde buscamos el máximo o el mínimo de una func ión donde existen o no un conjunto de restricciones. Sin embargo, un problema de optimización combinatoria puede también ser formulado de manera más relajada como sigue:
Dado un problema de optimización, podemos encontrar el costo de la solución óptima.
Se sabe que dado un problema de optimización, se puede definir un problema de decisión asociado a él, esto es, una pregunta que puede ser contestada por si o no. Por otro lado, varios problemas computacionales bien conocidos son problemas de decisión. Entre los problemas de decisión se pueden mencionar por ejemplo:
- El problema de paro (Halting Problem ): dado un algoritmo y su entrada, ¿Parará éste alguna vez?
- El problema de satisfactibilidad: dada una fórmula booleana, ¿Es ésta satisfactible?
- El problema del circuito Hamiltoniano: dado un grafo G, ¿Hay un circuito en G que visite todos los nodos exactamente una vez?.
La definición de problema de decisión a partir del problema de optimización permite estudiar ambos tipos de problemas de una manera uniforme.
Además, como se ha puntualizado que un problema de decisión no es más difícil que el problema de optimización original, cualquier resultado negativo probado sobre la complejidad del problema de decisión será aplicable al problema de optimización también. Se está interesado en clasificar los problemas de decisión de acuerdo a su complejidad. Se denota por P a la clase de problemas de decisión que son polinomialmente acotados, esto es, la clase de problemas de decisión que pueden ser solucionados en tiempo polinomial. La clase P puede ser definida muy precisamente en términos de cualquier formalismo matemático para algoritmos, como por ejemplo la Máquina de Turing.
Se puede decir que P es la clase de problemas de decisión relativamente fáciles, para los cuales existe un algoritmo que los soluciona eficientemente. Para una entrada dada, una “solución” es un objeto (por ejemplo, un grafo coloreado) que satisface el criterio en el problema y justifica una respuesta afirmativa de si. Una “solución propuesta” es simplemente un objeto del tipo apropiado, este puede o no satisfacer el criterio. Informalmente se puede decir que NP es la clase de problemas de decisión para los cuales una solución propuesta dada para una entrada dada, puede ser chequeada rápidamente (en tiempo polinomial) para ver si ésta es realmente una solución, es decir, si ésta satisface todos los requerimientos del problema.
Una solución propuesta puede ser descrita por una cadena de símbolos a partir de algún conjunto finito. Simplemente se necesita alguna convención para describir grafos, conjuntos, funciones, etc. usando estos símbolos. El tamaño de la cadena es el número de símbolos en ella. Chequear una solución propuesta incluye chequear que la cadena tenga sentido (esto es, que tenga una sintáxis correcta) como una descripción del tipo de objeto requerido, también como chequear que ésta satisface el criterio del problema.
Algoritmos No Determinísticos
Un algoritmo no determinístico tiene dos fases:
Fase no Determinística: alguna cadena de caracteres, s, completamente arbitraria es escrita a partir de algún lugar de memoria designado. Cada vez que el algoritmo corre, la cadena escrita puede diferir (Esta cadena puede ser vista como una adivinación de la solución para el problema, por lo que a esta fase se le da el nombre de fase de adivinación, pero s también podría ser
ininteligible o sin sentido).
Fase Determinística: Un algoritmo determinístico (es decir ordinario) siendo ejecutado. Además de la entrada del problema de decisión, el algoritmo puede leer s, o puede ignorarla. Eventualmente éste para con una salida de si o no, o puede entrar en un ciclo infinito y nunca parar (véase ésta como la fase de chequear, el algoritmo determinístico verifica s para ver si ésta es una solución para la entrada del problema de decisión).
El número de pasos llevados a cabo durante la ejecución de un algoritmo no determinístico es definido como la suma de los pasos en ambas fases; esto es, el número de pasos tomados para escribir s (simplemente el número de caracteres en s) más el número de pasos ejecutados por la segunda fase determinística.
Normalmente cada vez que se corre un algoritmo con la misma entrada se obtiene la misma salida. Esto no ocurre con algoritmos no determinísticos; para una entrada particular x, la salida a partir de una corrida puede diferir de la salida de otra debido a que ésta depende de s. aunque los algoritmos no determinísticos no son realistas (algoritmos útiles en la práctica), ellos son útiles para clasificar problemas.
Se dice que un algoritmo no determinístico es polinomialmente acotado si hay un polinomio p tal que para cada entrada de tamaño n para la cual la respuesta es si, hay alguna ejecución del algoritmo que produce una salida si en cuando mucho p(n) pasos.
De esta forma se puede decir que: NP es la clase de problemas de decisión para los cuales hay un algoritmo no determinístico acotado polinomialmente (el nombre de NP viene de no determinístico polinomialmente acotado).
Un algoritmo ordinario (determinístico) para un problema de decisión es un caso especial de un algoritmo no determinístico. En otras palabras, si A es un algoritmo determinístico para un problema de decisión, entonces A es la segunda fase de un algor itmo no determinístico. A simplemente ignora lo que fue escrito por la primera fase y procede con su cálculo usual. Un algoritmo no determinístico puede hacer cero pasos en la primera fase (escribiendo la cadena nula). Así, si A corre en tiempo polinomial, el algoritmo no determinístico con A como su segunda fase corre también en tiempo polinomial. De lo mencionado se deduce que P es un subconjunto propio de NP.
La gran pregunta es ¿ P = NP o es P un subconjunto propio de NP? Se cree que NP es un conjunto mucho mayor que P, pero no hay un solo problema en NP para el cual éste haya sido probado que el problema no está en P. No hay un algoritmo polinomialmente acotado conocido para muchos problemas en NP, pero ningún límite inferior mayor que un polinomio ha sido probado para estos problemas.
NP-completo es el término usado para describir los problemas de decisión que son los más difíciles en NP en el sentido que, si hubiera un algoritmo polinomialmente acotado para un problema NP-completo, entonces habría un algoritmo polinomialmente acotado para cada problema en NP.
Y fin, queda una sola publicación con un índice para repasar todos los temas.
