Diego Delgado Martínez
Cuando me asignaron esta entrada de blog el
título que se me asignó fue “¿P=NP?”, y primera reacción fue: “No esperarán que
responda a esa pregunta”. El problema de P frente a NP es considerado uno de
los siete problemas del milenio, y por tanto todavía no se le ha encontrado
solución. Aunque se han dado aproximaciones y soluciones, ninguna de ellas se ha considerado válida por la comunidad científica.
Ilustración 1: El problema P=NP ha
aparecido en series como The Simpsons, Futurama o Numb3rs
¿Qué significa P=NP? ¿Qué es este problema?
Un algoritmo para resolver un problema es eficiente si su coste, en tiempo, es un polinomio en función del tamaño de los datos de entrada. La clase de problemas para los que existen algoritmos que los resuelven de forma eficiente (en tiempo polinomial) se denomina clase P. Hay problemas para los que una posible solución se puede verificar en tiempo polinomial (hay un algoritmo en P que decide la validez de una solución). Este tipo de problemas se encuentran en la clase NP (problemas resolubles de forma no determinista en tiempo polinómico). El problema P versus NP trata de estudiar si es cierto o no que P=NP, es decir, que todo problema para el que se puede verificar eficientemente su solución es un problema para el que se puede calcular su solución de forma eficiente (en tiempo polinomial de manera determinista).
P contiene a
la mayoría de problemas naturales. Por ejemplo suma de números, problemas de
programación lineal, conectividad en grafos no dirigidos, etc. Las siglas NP
pertenecen a “Nondeterministic Polynomial time”, y se refieren los problemas de
decisión que pueden ser resueltos en un tiempo polinomial por un autómata o máquina de Turing no determinista. Un ejemplo de esta clase de complejidad es el
problema de decisión basado en el problema del viajante, consistente en encontrar un ciclo hamiltoniano con un coste menor que una constante dada. El problema del viajante también es conocido por sus siglas en inglés TSP (Traveling Salesman
Problem).
Este problema plantea cómo un
viajante podría empezar y terminar en la misma ciudad, pasando por todas las
ciudades que están en su mapa una sola vez, con una cantidad de kilometros totales menor que una constante dada. Es fácil comprobar que este problema tiene un coste n!, es
decir, n! caminos distintos que hay que comprobar si son ciclos hamiltonianos y
además con coste menor que k. Este problema es NP- completo, que es una de las subclases más “difícil”
dentro de los problemas que consideramos NP. Pongamos un ejemplo, imaginemos
que este problema con sólo 20 ciudades, las posibles combinaciones de estas
ciudades serían más de 2.4 trillones (20!).
El problema del viajante consiste en encontrar el camino mínimo en las circustancias anteriores. Este problema es NP-hard, complejidad mayor que NP-completo.
Para todos los problemas de tipo
NP, si se nos diera una posible solución afirmativa, se podría comprobar esta
solución en tiempo polinómico. En el ejemplo anterior del TSP, bastaría con
comprobar que la solución se compone de n nodos no repetidos y que el último es
adyacente al primero. Que P=NP, significa que para cada problema para el que
podemos verificar su solución eficientemente (en tiempo polinómico), podemos
hallar esta solución también en tiempo polinómico.
Es importante señalar que los
problemas NP-completos son equivalentes entre sí. De tal manera que si se
encuentra un algoritmo eficiente para uno de ellos, también se obtiene para
todos los demás. Actualmente se conocen cientos de problemas NP-completos (y
cientos de demostraciones falsas de que estos se encuentran en P).
¿Qué pasaría si P=NP?
Técnicamente,
esto podría ser verdad, así que imaginemos que gracias a esto, podremos
encontrar solución a problemas muy difíciles, como los NP-completos,
rápidamente. Algunos puntos de vista se centran sólo en lo negativo, por
ejemplo, si P=NP el encriptado de claves sería inútil, ya que tendríamos algoritmos
muy eficientes que lo desencriptarían rápidamente.
Pero
todos los problemas que hoy no se pueden resolver, al menos en un tiempo
aceptable, serían posibles. Por ejemplo, y rascando la superficie de lo
posible, la solución al problema del viajante antes expuesto haría el trasporte
mucho más eficiente, las fábricas aumentarían enormemente su productividad y a
un coste menor. Las máquinas aprenderían rápidamente, los algoritmos de
aprendizaje como el reconocimiento de objetos o el aprendizaje del lenguaje se volverían
problemas triviales.
Enfoque P ≠ NP
Lo que creo que ha quedado claro es que nadie entiende en realidad completamente este problema, y que se ha arañado solo la superficie de lo posible. Este problema parece que va a ser un misterio hasta dentro de muchos años.
Tras esto decir que la gran
mayoría de expertos en teorías de complejidad apoyan que NP es distinto de P y
que su demostración es sólo cuestión de tiempo.
A continuación muestro un par de
métodos destacados con los que se ha abordado el tema y han fallado en la
demostración.
- Diagonalización. ¿Podemos construir un lenguaje NP ‘L’ tal que cada algoritmo que funcione en tiempo polinómico falle al computar ‘L’? Este es el enfoque de la diagonalización, el cual se remonta al siglo XIX, donde Georg Cantor demostró que no es posible enumerar los números reales.
Alan Turing, en su artículo “On Computable Numbers, with an Application to the Entscheidungsproblem”[8] en 1936 demostró mediante diagonalización que el problema de parada (Halting Problem), no es computable por una máquina de Turing.
- Complejidad de circuitos.
Para demostrar que P ≠ NP basta con demostrar que algún problema NP-completo no puede ser resuelto por un circuito relativamente pequeño de puertas AND, OR y NOT (es decir, que el número de puertas venga determinado por la entrada en una función polinomial).
En 1985 Razborov demostró que para el problema de la cliqué (encontrar un subgrafo de tamaño k donde todos sus vértices son adyacentes entre sí, problema NP-completo) no existe un circuito pequeño si sólo se usan puertas AND y OR. Pero al introducir las puertas NOT en sus técnicas, todo falla. En los casi 30 años que llevamos desde aquello todavía no se ha encontrado un circuito que reduzca significativamente el número de puertas necesarias.
Lidiando con los problemas NP
Tenemos un problema NP-completo
que queremos resolver, si, como creemos, P ≠ NP, este problema no tiene una
solución eficiente. Pero el problema sigue estando ahí, y seguimos necesitando
resolverlo. Existen métodos para calcular la solución o al menos acercarnos a
ella. Los más reseñables son:
- Fuerza bruta. Los ordenadores de hoy en día no son los mismos que hace 30 años ni mucho menos como las primeras máquinas de Turing. La velocidad de cómputo ha aumentado considerablemente, de modo que, para entradas pequeñas, podemos resolver problemas NP en un tiempo considerable, e incluso con algunos algoritmos inteligentes problemas con una entrada moderadamente grande. Por ejemplo, para el problema del viajante, con el método de planos de corte (Cutting Plane Method) de Gomory, lo podemos resolver en práctica con más de 10.000 ciudades.
- Complejidad parametrizada. Downey y Fellows iniciaron un análisis de la complejidad computacional para ciertos problemas de decisión parametrizados. El interés de este estudio reside en aquellos problemas NP-completos pero que tienen complejidad polinomial cuando el parámetro k es fijo. Para algunos problemas como el problema de la cliqué el mejor algoritmo conocido requiere
- Aproximación. No podemos esperar resolver estos problemas de manera eficiente, pero a veces nos basta con una aproximación que si podemos obtener de manera eficiente. Por ejemplo, para el problema del viajante, Arora en el 2000 aproximo la solución con un coste de
.
- Heurísticas y complejidad para casos promedio. El estudio de los problemas NP se centra en estudiar su comportamiento ante la peor entrada posible, pero en la realidad no siempre es así. Algunos de estos problemas con entradas realistas se pueden resolver de manera moderadamente fácil por medio de heurísticas.
Ya hemos visto que
pasaría si P=NP, pero, si como creemos esto no es así, podemos asumir los
problemas NP-c como una herramienta muy útil, sobre todo en criptografía.
Asumiendo que P≠NP podemos crear fuertes algoritmos para encriptar claves y
documentos.
¿Podrán los ordenadores cuánticos resolver los problemas NP-completos?
En pocas palabras, los expertos
lo dudan bastante. Lov Grover encontró un algoritmo cuántico que funciona para
todos los problemas NP pero sólo consigue una mejora cuadrática y hay
evidencias que de esa aceleración no se puede mejorar.
Una nueva esperanza
Ketan Mulmuley y Milind Sohomi
[9] han abordado el problema desde la perspectiva de la geometría algebraica,
mediante la Teoría de la Complejidad Geométrica (GCT). Esta perspectiva parece
no tener los problemas que han tenido otros modos de abordar el problema, pero
necesita unas matemáticas muy complejas que pueden llevar años o décadas sacar
adelante. Esto da una nueva esperanza para resolver el problema. Aun así,
Mulmey afirma que este proceso llevará unos 100 años, si es que al final
funciona.
Conclusión
Hemos abordado el problema desde
diferentes puntos de vista y el porqué es importante demostrar que P≠NP. La
gran mayoría de métodos no pueden ser explicados de manera sencilla, necesitan
matemáticas bastante complejas, por lo que no he podido incluir tantas como me
gustaría ni reducir el tamaño de esta entrada de blog.Lo que creo que ha quedado claro es que nadie entiende en realidad completamente este problema, y que se ha arañado solo la superficie de lo posible. Este problema parece que va a ser un misterio hasta dentro de muchos años.
Diego Delgado Martínez
Referencias y Bibliografía:
- Stephen Cook, “The P versus NP problem”, 2000
- Lance Fortnow, “The Status of the P versus NP Problem”, Northwestern University, 2009
- Francisco R.Villatorio, “El estado actual del problema P distinto de P”,2009
- Pablo Burzyn, “Complejidad Computacional en problemas de modificación de aristas en grafos”
- Artículo “What will happen when P≠NP Is Proved?”
- “Polynomial time Aproximation scheme for Euclidean Traveling Salesman”
- Problema del viajante.
- Alan Turing, “On Computable Numbers, With An Application to the Entscheidungsproblem”, 1936.
- Ketan D.Mulmuley, “The GCT program towards the P vs. NP problem”, 2012
Invitación a verificar posible solución analógica de SSP https://pnpanalogo.wordpress.com/2016/01/14/22/
ResponderEliminar