16 de agosto de 2010

La importancia de P vs NP

Figura de Theory Matters Wiki.

Dado los acontecimientos de la semana que acaba de terminar, donde Vinay Deolalikar presentó un intento de prueba para el problema de P vs NP, esta entrada la escribo para poder explicar los alcances del problema mismo para las ciencias de la computación, y para todas las ciencias en general.

Cada mes se publican en ArXiv artículos que dicen resolver el problema. Algunos dicen que P=NP, otros que P≠NP, etc. La diferencia estuvo en que este artículo en particular había pasado todos los exámenes que utilizan los teóricos en complejidad para discriminar los artículos serios. Además, este estaba escrito por una persona conocida, y cuando  había enviado una versión preliminar a un grupo selecto de científicos, uno de los principales, el mismo descubridor del problema y ganador del premio Turing, Stephen Cook, había escrito en respuesta "esto parece un esfuerzo serio" (del inglés this looks like a serious effort). Esto había motivado al resto y puso a funcionar una máquina bien aceitada de colaboración científica inigualable en la red. Como lo dijo Dick Lipton, "lo que antes se hacía en meses, ahora por Internet lo hacemos en días". Para saber como terminó toda la historia recomiendo el post anterior de Alejandro donde tienen todos los enlaces. Aquí me voy a concentrar en la definición e importancia de P vs NP.

A continuación un pequeño repaso del problema. Antes que nada este es considerado el problema principal, más importante, de las ciencias de la computación. Básicamente el problema es "para ciertos problemas, lo mejor que podemos hacer es una búsqueda bruta", o como escribe Lipton "para ciertos problemas el algoritmo más obvio es el mejor". NP como sabemos quiere decir "tiempo polinomial no-determinístico", y P "tiempo polinomial determinístico". Entonces los problemas o lenguajes con algoritmos que corren en tiempo polinomial están en P, y los problemas con algoritmo en tiempo polinomial no-determinístico en NP.

Una caracterización más fácil de entender de problemas en NP es la siguiente: Sea A un algoritmo que tiene dos entradas, x que representa una instancia de un problema L (e.g. SAT, TSP, etc), y c que representa una solución al problema. Entonces L están en NP si y solo si existe un algoritmo determinístico que corre en tiempo polinomial A y existe un c tal que A(x,c)=1, i.e. que c sea una respuesta válida al problema. Generalmente a c se le llama solución, certificado, testigo o simplemente prueba, i.e. una prueba de que x tiene solución. La misma caracterización se puede hacer para P, pero esta vez el algoritmo no tiene una prueba c. Entonces decimos que L está en P si y solo si existe un algoritmo determinístico que corre en tiempo polinomial A  tal que A(x)=1.

La gran diferencia está en el certificado. Los algoritmos para lenguajes en P determinan una solución, mientras que los algoritmos para lenguajes en NP verifican una solución. Una buena analogía es: si yo resuelvo un problema matemático por mi mismo (está en P), o estoy verificando la solución de otra persona (en NP). Entonces, la diferencia radica en que estamos comparando un proceso de determinar una solución a un problema contra un proceso de verificación de una solución ya dada para un problema.

Imagen de Wikipedia.

P vs NP en términos computacionales se refiere a cotas inferiores de problemas NP-completos. La conjetura es que para estos problemas no existe un mejor algoritmo que el de fuerza bruta, i.e. P≠NP. La mayoría de los científicos creen que esto es cierto, y de ahí surgen un montón de alternativas para resolver problemas NP-completos como Búsqueda Local, Algoritmos Genéticos, etc. Y la eficiencia de estos métodos está en que pueden verificar soluciones en tiempo polinomial.

En mi humilde opinión, una prueba de que P≠NP no cambiaría mucho las cosas porque todo lo que hacemos ahora, lo hacemos en función de que P≠NP. Por ejemplo, asumimos la existencia de 1-way functions en criptografía ¿Entonces de que nos sirve una prueba de eso? Una prueba no solo nos dice si una hipótesis es falsa o verdadera, sino que al mismo tiempo ganamos mucha información acerca del problema mismo. De una prueba de P≠NP podemos descubrir muchas conexiones entre áreas de conocimiento u objetos que creíamos desconectados en nuestra teoría. Eso tiene mucho más valor que una respuesta de falso o verdadero. Esto es lo que está ocurriendo con la prueba de Deolalikar. Algunas personas nunca habían considerado conectar el finite model theory con el clustering en Random-k-SAT. El enfoque de por sí requiere más investigación y despierta mucha curiosidad.

En el aspecto filosófico, P vs NP hace la siguiente pregunta: ¿Puede la creatividad ser automatizada? Si yo escribo un libro en el que trabaje 1 año, y lo mando a un periódico para que un crítico lo lea, y la destruye completamente en 2 semanas, ¿Qué es más dificil, escribir el libro o criticar el libro? Intuitivamente el proceso creativo es más complejo y requiere más tiempo, pero hasta que no tengamos una prueba que indique sin duda alguna nunca sabremos, por la misma razón que expuse en el párrafo de arriba. Simplemente por la curiosidad del hombre, tenemos que saber (esto lo dijo David Hilbert). 

También la misma pregunta se extiende a otros ámbitos como la física. La visión de las ciencias de la computación y una parte de la comunida de físicos, es que toda nuestra realidad física es computable. Desde la evolución de los seres vivos, hasta la formación de galaxias. Todo es visto como un proceso que dado una entrada genera un salida. Entonces salen preguntas como ¿Qué tan complejo es el plegado de proteínas? ¿Qué pasa con la información y la energía en un hoyo negro que se disipa en forma de radiación de Hawking? etc, etc. Muchas de esta preguntas están siendo respondidas por técnicas de ciencias de la computación. Por ejemplo, sabemos que si P≠NP entonces no podemos viajar en el tiempo, o no podemos movernos más rápido que la luz, y otras conexiones más extrañas. Aún así, estás conexiones dan evidencia a favor de que P≠NP, o no?

Asi que P vs NP no solo se refiere a problemas que solo interesan a las ciencias de la computación. Se refiere también a problemas fundamentales de otras ciencias. Inclusive podría decirse que es una de las preguntas más fundamentales de las matemáticas. Saber si podemos encontrar pruebas eficientemente nos da conocimiento de como resolver otros problemas muy difíciles como la Hipótesis de Riemann. Es por ello que el Clay Mathematics Institute lo pone en su lista de problemas fundamentales.

Para más información recomiendo el libro Computational Complexity A Modern Approach, o el artículo de Lance Fortnow en Communications of the ACM.

10 de agosto de 2010

Una prueba de que P ≠ NP?

Desde hace unos días Vinay Deolalikar ha creado un gran revuelo en la comunidad científica al liberar un borrador de una prueba de que P ≠ NP. La pregunta de si P es igual o distinto a NP es uno de los problemas no resueltos más importante de las ciencias de la computación (y las matemáticas), por lo tanto, el borrador de Vinay ha tenido a la comunidad científica ocupada tratando de verificar sus 102 páginas.

Por mi parte sólo estoy tratando de seguir las discusiones, no creo ser la persona capacitada para analizar la veracidad o falsedad de las afirmaciones de Vinay, así que aquí dejaré algunos links para quienes estén interesados en seguir el debate.

Sin dudas los posts en el blog de Dick Lipton son los más interesantes:
También hay un intento de ordenar la discusión por medio de una Wiki en el sitio de Michael Nielsen.

A pesar de los problemas marcados, aún no hay un "veredicto" definitivo de la comunidad científica, más allá de alguna apuesta, la mayoría coincide en que la prueba puede ser correcta, o al menos llevar a un razonamiento correcto, con los errores esperables en un borrador tan largo en un problema tan complejo y lo que todos coinciden, es en que es un muy buen trabajo y tiene resultados interesantes, aún si la prueba de P ≠ NP resultase errónea.

Update 11/08/10: Un nuevo post en el blog de Dick Lipton trata de tirar más luz al asunto: La idea es pedirle a Vinay que muestre cómo usar sus resultados para resolver problemas más sencillos, de los cuales ya se conoce la solución. Es una buena manera de entender por dónde viene la mano, ya que el paper en sí tiene muchos detalles técnicos y es difícil de seguir incluso por quienes trabajan a diario en complejidad.

Update 11/08/10 (2): Dejo un artículo de divulgación muy bueno que apareció en la revista Nature: Million-dollar problem cracked?

Update 12/08/10: Un nuevo post en el blog de Dick Limpton detalla cuál parece ser el mayor problema en la prueba, y la respuesta de Vinay Deolalikar.

Update 13/08/10: Dick posteó lo que parece ser un error insalvable en la prueba, un error de interpretación por parte de Vinay en el uso de la teoría de modelos finita: Fatal Flaws in Deolalikar’s Proof?