Una copa de cava y la demostración de P≠NP de Vinay Deolalikar

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

He cenado con cava y sigo con cava. Vinay Deolalikar, nacido en 1971 en Nueva Delhi, India, doctor en ingeniería eléctrica y matemáticas, afiliado a HP Research Labs, Palo Alto, California, envió un artículo el 6 de agosto de 2010 (102 páginas a 12pt) a investigadores de renombre en varias áreas. Afirma haber demostrado que P≠NP y que el manuscrito ha acabado en internet sin su permiso. Así que ha decidido publicar él mismo el pdf en su web (103 páginas ahora mismo). Varios expertos creen (y lo comentan en la web) que la demostración tiene buena pinta y parece un ataque a la conjetura realmente serio. Así que no me queda otro remedio que leerme la demostración. ¡Asustan 103 páginas! Supongo que no me enteraré de nada…

Bueno, antes de lanzarme al ruedo voy a recurrir a la opinión de  Scott Aaronson, «Putting my money where my mouth isn’t,» Shtetl-Optimized, August 9th, 2010. «El manuscrito de Deolalikar está bien escrito y presenta la historia, los antecedentes y las dificultades asociadas al problema P vs NP de forma muy competente.» Bueno, como es de esperar ya que por algún sitio he leído que lleva varios años trabajando en este problema. Confiesa Scott que «todavía no he encontrado la oportunidad de estudiar este manuscrito de 103 páginas en detalle. Además , no voy a interrumpir mis vacaciones para hacerlo, a menos que los expertos que están estudiando los detalles del artículo desde el primer día me digan que debo hacerlo.» Queda claro que habrá que estar atento a Shtetl-Optimized.

La demostración de Deolalikar utiliza física estadística. Física estadística aplicada al modelado de ciertos problemas sobre lógicas de primer orden que modelan la búsqueda de soluciones de problemas de satisfacción de restricciones (problemas k-SAT). Una demostración de un resultado matemático tan importante como P≠NP utilizando técnicas de física estadística erizará los pelos de los matemáticos ya que es posible que algún «teorema» de física estadística utilizado en la demostración puede que no sea un «teorema» de matemáticas. Ya sabéis que para los matemáticos las demostraciones de los físicos no son fetén fetén. Así que habrá que cruzar los dedos y confiar en que la demostración no acabe siendo un nuevo enfoque físico a la conjetura P≠NP.

Quinta y última copa de cava (no soy el único que bebe cava en casa). Espero que mi resumen no me quede demasiado mal. Ya se sabe, el cava… El resumen de la prueba («synopsis of proof«) aparece en las páginas 5-11 del artículo. Tiene buena pinta tras una primera lectura. Pero un resumen es solo eso, un resumen.

La idea es encontrar un problema NP-completo que no se pueda descomponer en un número polinomial de subproblemas en P. Deolalikar considera el problema k-SAT. El problema de satisfacer una fórmula booleana con k bits escrita en forma normal conjuntiva. La clase NP es la clase de problemas cuya solución requiere un coste (número de pasos o tiempo de cómputo) no polinómico pero para los que la verificación de una solución solo requiere un número polinómico de pasos. La clase P es la clase de problemas que se pueden resolver en coste polinómico en el tamaño de la entrada. La clase de  problemas NP-completos es un conjunto de problemas NP que son equivalentes entre sí en el sentido de que obtener un algoritmo en P para resolver uno de estos problemas  permite obtener un algoritmo para resolverlos todos. El problema k-SAT es un problema NP-completo para k>=3.  

Deolalikar considera el problema k-SAT elegido aleatoriamente que puede expresarse como un problema búsqueda (en número exponencial, no polinómico)  y cada búsqueda como un fórmula de la lógica de primer orden. La solución del problema k-SAT corresponde a un punto fijo en la búsqueda. Un problema clásico llamado FO(LFP). La prueba procede por reducción al absurdo. Si asumimos que NP=P y aplicamos ciertas técnicas de física estadística para el análisis de los NP problemas de búsqueda resulta que los problemas de búsqueda deben cumplir ciertas propiedades técnicas que contradicen a ciertos resultados bien conocidos sobre la física estadística de un problema k-SAT aleatorio. Por reducción al absurdo resulta que P≠NP. 

La demostración se basa en aplicar ideas de física estadística en el contexto de la teoría de modelos gráficos probabilísticos y la teoría de modelos finitos (que permite caracterizar la clase de complejidad PTIME o de problemas resolubles en tiempo polinómico). Para ello se utiliza un teorema de la llamada teoría de réplicas que asocia una distribución de probabilidad conjunta a todas las posibles instancias del problema. Esta distribución conjunta es factorizable en distribuciones más sencillas si dicha distribución cumple ciertas propiedades técnicas (teorema de Hammersley-Clifford). Las distribuciones de probabilidad más sencillas corresponden a problemas que cumplen con las restricciones del problema. El problema original para las instancias asociadas a estas distribuciones de probabilidad más sencillas es de coste polinómico. 

Bueno, no puedo contar mucho más. Necesito una lectura más detallada y una mente más fresca. Habrá que estar al loro los próximos días para ver como acaba este asunto…



8 Comentarios

  1. Hola, la verdad es que cuando leí la noticia en Slashdot me emociné muchísimo, hay pocos acontecimientos al largo de la historia que hacen que los libros (en este caso de computación) cambien de verdad, y este es uno de ellos.

    Sólo un par de apuntes: «La clase NP es la clase de problemas cuya solución requiere un coste (número de pasos o tiempo de cómputo) no polinómico pero para los que la verificación de una solución solo requiere un número polinómico de pasos.» Creo que es mejor la definición: la clase NP corresponde a los problemas cuya solución puede calcularse en tiempo polinómico en una máquina de Turing No Determinista (MTND), pero la solución puede verificarse en tiempo polinómico utilizando una máquina de Turing Determinista (MTD).

    Sobre la clase NP-Completo yo diría que es la clase de problemas NP que son tan difíciles de resolver como cualquier otro problema NP. Esto es que un problema NP es NP-Completo si cualquier instancia de cualquier problema NP puede reducirse en tiempo polinómico en una MTD a éste.

    Imagino que cuando escribiste el artículo lo hiciste con afán divulgativo, pero como siempre he visto esta página como una web de divulgación «avanzada» creo que sería mejor definir estos conceptos más estrictamente.

    Sobre el resto de conceptos no relacionados con la complejidad, no te puedo decir nada, ¡no tengo ni idea! 😛

    Un saludo.

    1. Gracias, Joan, tienes razón, mis definiciones no son muy rigurosas. Un lector que sepa lo que es una MTND y en qué se diferencia de una MTD, seguramente también sabrá que es un problema NP-c y en que se diferencia de uno NP. Aún así trataré en futuras entradas sobre este teorema tratar de ser más riguroso con las definiciones.

    2. Una máquina de Turing es un programa (algoritmo) que realizando diversas operaciones (ciclos) genera un resultado. Solo los algoritmos deterministas dan siempre un resultado correcto, los no deterministas (MTND) esperamos que den resultados correctos muchas veces pero no siempre.

      En lenguaje llano, debemos decir que NP es aquel conjunto de problemas que para resolverlos con seguridad con un algoritmo hay que realizar un número de operaciones que aumenta de manera exponencial según el número de variables que intervienen en el problema, pero que con algún algoritmo es posible obtener muy a menudo el resultado correcto (aunque no siempre) en un número de operaciones proporcional (crecimiento lineal o asintótico decreciente) al número de variables que intervienen en el problema.

      Si un problema NP se puede resolver con un algoritmo determinista en P en realidad ese problema era de tipo P y nunca fue NP. Basta con encontrar un solo caso que P=NP para demostrar que los problemas NP no existen y que todos son P, aunque desconozcamos el algoritmo particular para cada uno que resuelva el problema siempre con un coste P.

      Por otra parte, no es conveniente hablar de tiempo sino de coste, en la resolución de problemas. Todo algoritmo (o máquina de Turing) se puede implementar en circuitos lógicos combinacionales, de tal modo que el coste en tiempo real de la resolución de un problema tipo NP será siempre el mismo y casi instantáneo, sin embargo el número de puertas lógicas (transistores) necesarias (y consumo de energía) para implementar ese circuito sería un exponencial del número de variables que intervienen en el problema. Con todos los transistores de un disco duro SSD de 1TB (8 billones con b de puertas lógicas), por ejemplo, tan solo podrían resolverse problemas NP de menos de 43 variables. Para resolver problemas NP de 50 variables, tan solo 7 más, harían falta 1000 discos duros de 1 Terabyte.

      1. Iñigo, te corrijo: «en lenguaje llano» un algoritmo está en NP si su solución se puede verificar con un algoritmo en P, pero ha de ser calculada con «un número de operaciones que aumenta de manera exponencial» en tiempo. «Basta con encontrar un solo caso» de un problema NP-completo que cumpla P=NP «para demostrar que los problemas NP no existen y que todos son P»; pero esto no es cierto para problemas de NP que no sean NP-completos. Por otro lado, hay dos tipos básicos de coste, en tiempo (número de operaciones), clase P, y en espacio (memoria de almacenamiento), clase PSPACE, estando P dentro de NP, y NP dentro de PSPACE, y PSPACE dentro de EXPTIME.

        Iñigo, creo que tienes que estudiar un poco de teoría de la complejidad.

        1. Jajaja, sí es verdad parece que nunca es suficiente.

          Lo del PSPACE y EXPTIME no suena mucho a «lenguaje llano». Por supuesto que ciertos algoritmos precisan de los dos tipos de costes (memoria y tiempo) para ser más óptimos, pero mas allá de la MT cualquier algoritmo tiene un equivalente lógico combinacional no secuencial, el cual puede dar la respuesta determinista en unos pocos milisegundos por lo que el tiempo es irrelevante; por eso creo (sugiero) que sería conveniente hablar solo de coste para evitar ambigüedades.

          Por lo demás permíteme (a riesgo de una debida reprimenda) la osadía de corregirte y ampliar el conocimiento del asunto . Un caso P=NP lleva implícito que el problema sea de tipo NP-duro, dado que solo los problemas NP-completos o NP-duros generalizan los problemas NP. Los NP-duro no se puede verificar con un coste polinómico, en cambio los NP que pueden dar un resultado correcto de manera no determinista la mayoría de las veces en tiempo polinómico se pueden verificar en tiempo polinómico. Sin embargo no sabemos con certeza si hay casos que se pueden verificar en tiempo polínómico problemas que no pueden ser resueltos de manera no determinista. Esto induce que, en el contexto de la conjetura PvsNP, en caso de que P=NP, algún problema de tipo NP-duro podrá ser resuelto de manera determinista con un coste polinómico, lo cual demostrará que todos los NP (y los NP-completo) en realidad son P.

  2. Hola,
    me ha impresionado la frase:
    «…The implications of this on applications
    such as cryptography, and on the general philosophical question of
    whether human creativity can be automated, would be profound.»

    ya que sería un puntazo que el trabajo de investigador se pudiera automatizar (aunque dicen de alguno que tiene una «plantilla» para papers)!

    Cuando he abierto el pdf, y leído la introducción lo primero que he hecho ha sido buscar la palabra «quantum», pero no aparece ni una sola vez.. así que me imagino que este problema está resuelto desde un punto de vista clásico, pero también habla de los spines de Ising… me esperaba alguna reseña en el blog de Michael Nielsen, coautor del libro «Quantum Computation and Quantum Information«. [En su web deja descargar el primer capítulo introductorio donde habla sobre el problema NP desde el enfoque de la información cuántica.]

    1. Asier, en relación al problema P vs NP, la computación cuántica tiene muy poco que aportar. Los algoritmos que están en la clase BQP pero no están en P (como los dos algoritmos de Shor para la factorización de números y el cálculo discreto de logaritmos) pocos creen que sean problemas NP-c (todavía no se sabe si lo son o no). Tampoco se conoce la relación entre BQP y NP. Así que poco puede aportar la computación cuántica al problema P vs NP (no he leído aún el capítulo de Nielsen que indicas pero no crea que afecte a lo que acabo de escribir).

  3. Jefe … acabo de encontrar este pequeño artículo http://3.ly/8m8m en el cual exponen algunos problemas con la demostración. Debido a que tienes mucho (mucho es mucho) mas conocimiento sobre esto que yo te lo dejo para que le des una mirada … 🙂

    Saludos

Deja un comentario