Ya hay una wiki para el análisis de la demostración de P≠NP de Deolalikar

Por Francisco R. Villatoro, el 11 agosto, 2010. Categoría(s): Ciencia • Informática • Matemáticas • Mathematics • Noticias • Science ✎ 1

Algunos de los mayores genios de la matemática están trabajando en la verificación de la demostración de Deolalikar, como el genial Terence Tao (que según su blog estaba de vacaciones), Timothy Gowers, Gil Kalai, Ken Regan y Suresh Venkatasubramanian, entre otros. Un grupo de grandes mentes pensantes que está estudiando la prueba de forma organizada y pública gracias a una wiki. Vinay (Deolalikar) se ha ofrecido a responder a todas las preguntas generadas en las discusiones de dicha wiki. La wiki «Deolalikar’s P!=NP paper» promete presentar todos los progresos sobre el análisis de la demostración y si aparecen errores menores podremos seguir los progresos para su solución, muy en la línea del proyecto Polymath.

En la blogosfera una de las mejores fuentes de información sobre el problema P≠NP es el blog de Dick Lipton llamado «Gödel’s Lost Letter and P=NP» que está dedicando un buen número de entradas a explicar en un lenguaje fácil la demostración de Deolalikar: «Update on Deolalikar’s Proof that P≠NP,» August 10, 2010; «Issues In The Proof That P≠NP,» August 9, 2010; y «A Proof That P Is Not Equal To NP?,» August 8, 2010. El lenguaje de Lipton no es tan fácil como el de Dana Chivvis, «P=NP=WTF?: A Short Guide to Understanding Vinay Deolalikar’s Mathematical Breakthrough,» AOL News, August 10, 2010, pero, seamos serios, ella se limita a explicar qué significan P y NP, y poco más.

Empecemos por Dana. Su artículo nos recuerda que «P significa «tiempo polinómico» y se refiere a un conjunto de problemas cuyas soluciones son fáciles de encontrar; NP significa «tiempo polinómico no determinista» y se refiere a un conjunto de problemas cuyas soluciones son difíciles de encontrar, pero fáciles de verificar; y Algoritmo es un conjunto de instrucciones utilizadas para resolver un problema. Usamos algoritmos sin pensar en ello en nuestra vida cotidiana, como cuando tratamos de averiguar por qué una bombilla no se enciende» [BTW no entiendo por qué Dana utiliza el ejemplo de cambiar una bombilla, cuando yo hubiera puesto el ejemplo de hacer un café o cocinar un huevo]. «Tiempo polinómico se refiere a que la ejecución de un algoritmo requiere muy poco tiempo, es «eficiente,» en concreto una potencia del tamaño de los datos necesarios para ejecutar el algoritmo. Los problemas en la clase «P» son aquellos cuyas soluciones se pueden obtener en tiempo polinómico. Los problemas en la clase «NP » son los que tienen soluciones que se pueden verificar en tiempo polinomial, pero se requiere un tiempo exponencial («mucho más tiempo») para obtener su solución.» El que quiera algo más, que se lea el artículo de Dana.

Los artículos de Richard Jay («Dick») Lipton son mucho más interesantes. El primero, 8 de agosto, aunque dice poco ha recibido más de 150 comentarios, muchos de los cuales son muy interesantes. Os recomiendo seguir los comentarios de KWRegan, de vloodin y de Lenka Zdeborova. Un comentario de vloodin indica que ha encontrado una hipótesis en la prueba que es discutible. Zdeborova nos recuerda que dicha hipóteis podría abrir una puerta trasera: un problema k-SAT podría tener ciertas simetrías «ocultas» que resbalarían entre los resquicios de la prueba de Deolalikar.

El segundo artículo de Dick, fechado el 9 de agosto, nos presenta 4 posibles problemas/errores en la demostración. Lo primero que nos recuerda es que la demostración se acaba de publicar en la web y nadie ha tenido tiempo todavía de estudiar con suficiente profundidad el artículo (de más de 100 páginas). Incluso si la demostración de Vinay Deolalikar contiene errores ha hecho una gran favor a la comunidad de matemáticos al compartir sus ideas con todos. Una tormenta de ideas (brainstorming) alrededor de su artículo podría resolver dichos problemas y conducir finalmente a la demostración correcta.

La demostración se basa en una reducción al absurdo. El autor proclama que P=NP implica la existencia de cierto algoritmo en P para cierto tipo de problemas k-SAT cuya existencia contradice ciertas propiedades estadísticas bien conocidas y demostradas rigurosamente de cualquier instancia de un problema k-SAT. Los problemas de la demostración apuntan a y convergen en la sección 7.2 del artículo. Los problemas son los siguientes:

1. Un problema encontrado por James Gate, Arthur Milchior y David Barrington y Lance Fortnow (ver también Barrington y Milchoir) es el siguiente. Todo problema NP se puede escribir mediante una fórmula de la lógica de primer orden gracias a la introducción de una relación de orden (<) adecuada, que siempre existe. Hay un teorema que caracteriza así la clase NP. Sin embargo, la clase P no se puede caracterizar tan fácilmente y es necesario que dicho orden exista, caracterización de P gracias a FO(LFP). Es un problema abierto (aún no resuelto y que parece muy difícil) determinar si es posible encontrar siempre dicho orden. Deolalikar compensa este defecto utilizando un retrueque técnico que le permite introducir un orden válido para los problemas k-SAT en P que el obtiene a partir de la suposición P=NP. Parece que no está claro si este truco funciona siempre para todos estos problemas como Deolalikar afirma. 

2. Otro problema encontrado por Paul Christiano y también Barrington es el siguiente. El artículo requiere que cierto predicado, fórmula lógica en FO(LFP), cumpla cierta propiedad (sea unario). Para que cumpla dicha propiedad, Deolalikar realiza una reescritura (reestructuración) de dicha fórmula para un problema k-SAT aleatorio que está basada en un procedimiento que utiliza una variable k’, pero no está claro si dicho procedimiento funciona cuando k’=k. Los argumentos de Deolalikar para garantizar que así sea parece que no están del todo claros.

3. La demostración de Deolalikar utiliza un teorema que podemos escribir crípticamente como FOL+LFP = P. La demostración de este teorema utiliza la técnica de la inducción y obtiene de forma constructiva una fórmula para cada problema en P. Sin embargo, Deolalikar usa este teorema sin recurrir a dicha construcción explícita y utiliza directamente la fórmula final (el punto fijo o FP de LFP) lo que genera ciertas dudas sobre si lo está usando correctamente o no (Christiano y KWRegan). Parece que está cuestión debería formar parte de la discusión presentada en la sección 7.2 pero no aparece.

4. Finalmente, hay un problema íntimo con la misma idea (método) de la demostración encontrado por Cris Moore y corroborado por Alif Wahid. La estrategia de la demostración parece aplicable solo a un subconjunto de todos los problemas k-SAT aleatorios posibles, un subconjunto grande, pero no a todos ellos. No está claro que la línea argumental de Deolalikar sea aplicable a todos ellos.

Estos cuatro problemas de la demostración no significan que la demostración sea incorrecta. La demostración es un primer boceto (first-draft) y es de esperar que contenga ciertos errores menores que tendrán que ser pulidos (así ocurrió ya con la demostración de Andrew Wiles del último teorema de Fermat y con el primer preprint de la demostración de Grisha Perelman de la conjetura de Poincaré). La cuestión importante es si la propia estrategia de la prueba es correcta. Si lo es, todos estos problemas serán resueltos en los próximos meses. Si no lo es, la demostración quedará como un gran alarde técnico a punto de lograr la gloria.

El tercer artículo de Dick trata de ayudar al estudio de la demostración de Deolalikar y su análisis, propiendo tres problemas relacionados con ella para los que las técnicas utilizadas en la demostración podrían ser prometedoras. Solo os comentaré el primer problema propuesto y os animo a los matemáticos a considerar también los otros dos.

Una de las ideas clave de la demostración de Deolalikar es la representación de algoritmos mediante fórmulas de la lógica de primer orden. Empecemos recordando la representación en árbol de una expresión aritmética en lógica booleana (que casi todo el mundo estudió en la parte de la Lógica de los cursos de Filosofía en Bachillerato). Estas expresiones usan variables lógicas que pueden valer 1 (verdad) y 0 (falso), y operadores de conjunción (y-lógica o ∧) y de disyunción (o-lógica o ∨). Por ejemplo, la fórmula de la figura de la derecha es ((α∧β∧γ∧δ)∨(α∧ζ∧θ)) y significa que es verdad o α y β y γ yδ (simultáneamente) o α y ζ y θ. Toda fórmula lógica se puede escribir en forma de árbol con una estructura similar a esta, una disyunción de conjunciones. Los que recuerden algo de lógica habrán estudiado este resultado. El tamaño de este árbol (número de hojas) es una función del número de variables (en la figura hay 6 variables y 7 hojas). En general una fórmula de este tipo tiene un número exponencial (no polinómico) de hojas como función del número de variables. Muchas fórmulas lógicas se pueden simplificar, por ejemplo, aplicando las leyes de Morgan, lo que conduce a un árbol asimétrico que tiene una profundidad mayor de 2 (como el de la figura). La profundidad es el mayor número de flechas que hay que recorrer para llegar desde la raíz (∨ en la figura) hasta cualquiera de sus hojas (las variables α, β, etc. en la figura). 

Dick nos propone considerar el subconjunto de todas las fórmulas lógicas llamadas fórmulas UTC (uniform tree computation). Son fórmulas que se pueden reescribir con un árbol más sencillo, pero asimétrico, que tenga un número de hojas que sea un polinomio en el número de sus variables, cuya profundidad (la del árbol) sea una constante fija y que cumple una condición técnica llamada «uniformidad» (en la que entraré). Dick nos propone demostrar que un problema k-SAT no puede ser resuelto mediante una fórmula UTC (un resultado ya conocido) utilizando las técnicas matemáticas utilizadas por Vinay en su nueva demostración. El problema considera Vinay en su demostración de P≠NP es algo más complejo.



1 Comentario

Deja un comentario