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?