La opinión de Terence Tao sobre la demostración de P≠NP de Deolalikar

La situación actual de la demostración de P≠NP de Dinay Deolalikar, a día de hoy, es la siguiente: la demostración es incorrecta y no puede ser corregida con cambios menores. La opinión general es que tampoco se puede corregir con cambios mayores, preservando la línea argumental de la prueba. Deolalikar afirma que ya está trabajando en ello. Por supuesto, la demostración parece muy interesante pero aún es pronto para saber si ofrece un nuevo camino para abordar problemas no triviales en la teoría de la complejidad. Aunque no permita demostrar P≠NP, son ideas nuevas que podrían ser muy fructíferas y el trabajo de Deolalikar no habrá caído en saco roto. El millón de dólares del Premio del Milenio ofrecido por el Instituto Clay sigue sin dueño. Así de duro nos lo cuenta Terence Tao, comentario del 11 de agosto de 2010 en el blog de R.J. Lipton, una de las fuentes más fiables sobre información en relación al problema P≠NP. Esta entrada se basa en parte en Scott Aaronson, “The ethics of scientific betting,” Shtetl-Optimized, August 11th, 2010.

Terry nos indica que la pregunta “¿es correcta la demostración de Deolalikar?” tiene tres enfoques diferentes y tres respuestas posibles.

1. ¿La demostración de Deolalikar, con pequeños cambios, es una demostración de P≠NP? No. El trabajo de muchos matemáticos durante los últimos días permite asegurarlo con rotundidad.

2. ¿La demostración de Deolalikar, con grandes cambios, es una demostración de P≠NP? Posiblemente no. Se requiere un número muy substancial de nuevas ideas en la línea argumental de la prueba.

3. ¿La línea argumental de la demostración de Deolalikar permitirá establecer nuevos resultados no triviales en la teoría de la complejidad? Todavía es pronto para saberlo. Los matemáticos que están estudiando la demostración también están estudiando con ahínco esta posibilidad. Terry es excéptico al respecto.

¿Cuál es el gran problema de la demostración de Deolalikar? La manera más sencilla de comprobar si una demostración de P≠NP es correcta es comprobar si aplicada a un problema NP-completo como 3SAT nos dice que no está en P, pero aplicada a un problema relacionado como 2SAT o XOR-SAT, que sí están en P, falla por algún lado. Deolalikar ha afirmado que está trabajando en ello y que espera poder obtener una demostración, valga la redundancia, de que su demostración falla en este tipo de problemas “fáciles.” Ahora bien, lo que está claro es que si has sido capaz de demostrar que ningún problema de NP está en P utilizando los problemas k-SAT te debería ser muy fácil mostrar la hipótesis de tu demostración que no cumplen problemas tan sencillos como 2SAT o XOR-SAT. Han pasado pocos días, pero Deolalikar solo ha respondido a estas preguntas con promesas vagas, lo está estudiando, pero el artículo es muy largo. Poca confianza inspiran estas palabras. Todo matemático sabe que si uno ha demostrado realmente P ≠ NP, debe ser capaz de explicar inmediatamente por qué la prueba no funciona para XOR-SAT. Más aún, la mayoría de los investigadores que han estudiado en detalle la prueba creen que Deolalikar no será capaz de resolver este gran hándicap, porque no se puede.

¿Os acordáis de lo que pasó con Perelman y los problemas técnicos de su primer manuscrito sobre la conjetura de Poincaré? Su gira americana en 2003, donde expuso su trabajo del 11/nov/2002 en múltiples universidades, tuvo como resultado que se descubrieran ciertos problemas de su demostración. Tras los primeros problemas, aparentemente graves, Perelman afirmó que los resolvería con absoluto convencimiento y continuaría con la gira como si nada. El 10/mar/2003 ya tenía publicado un nuevo artículo con la solución y siguió su gira, cual “flamenca.” Surgieron aún más problemas, que también resolvió con maestría y convicción (su tercer y último artículo es del 17/jul/2003). Ya acabada su gira americana prometió un último artículo sobre las últimas coletillas que le quedaban por resolver. Pero eran tan “sencillas” para él que ni se molestó en escribir el artículo. Sabía que otros lo harían por él (Colding y Minicozzi lo hicieron el 10/ago/2003). En septiembre de 2003 ya estaba publicado todo lo necesario para quien quisiera (y pudiera) pasara toda la demostración de Perelman a limpio. Hubo que esperar casi 3 años para que en 2006 ya pudiéramos leer la demostración de la conjetura de Poincaré de Hamilton-Perelman escrita en limpio.

1 Comentario

Participa Suscríbete

Juan Manuel Dato Ruiz

¡Qué suerte tener poder mediático para ser escuchado! Los hay que tienen que construir el coche antes que el diseño… En cualquier caso, malo sería que un hacker supiera de la realidad antes que los que tienen los poderes mediáticos.

Deja un comentario

Tu email nunca será mostrado o compartido. No olvides rellenar los campos obligatorios.

Obligatorio
Obligatorio
Obligatorio

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>