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

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…

Este fin de semana se ha obtenido un nuevo récord de luminosidad en el LHC del CERN que avanza viento en popa

Este fin de semana (7-8 de agosto) el LHC del CERN ha logrado un nuevo récord de luminosidad pico (número de colisiones por segundo). Ya permite que cada haz contenga 25 paquetes de protones y el objetivo óptimo este año es alcanzar 750 (384 según un artículo en ICHEP 2010) paquetes por haz. En marzo del año próximo el LHC debería alcanzar 796 paquetes de protones por haz para garantizar que a finales de año se cumplan todos los objetivos plenamente. El LHC del CERN avanza viento en popa y a toda marcha. ¡Enhorabuena a todos los que trabajan en el CERN! Para los aficionados a números más técnicos os indicaré que el récord alcanzado este fin de semana ha sido una luminosidad pico o instantánea equivalente a 0’13 /fb/año (inversos de femtobarn al año). Para lograr el objetivo del LHC para el próximo año (2011), que es obtener 1/fb de colisiones acumuladas, se deberá lograr este año una luminosidad pico mantenida de unos 0’13/fb/mes (en LHC funcionará entre febrero y octubre, unos 8 meses). Este año el LHC funcionará hasta octubre (en colisiones protón-protón, después colisionará durante un mes iones pesados). Nadie duda que el LHC logrará alcanzar en los próximos 3 meses una luminosidad pico 12 veces mayor que la actual. Ya ha logrado incrementos mayores en sus primeros cuatro meses y el LHC está funcionando mejor de lo esperado. Este fin de semana también hay que celebrar que el LHC ha logrado acumular un número total de colisiones de 1/pb, 1000 veces menos que lo que tendrá que lograr el año que viene (ATLAS y CMS alcanzarán este número esta semana en curso). Buenas noticias para todos los que seguimos al LHC. Nos lo han contado en todos los foros que siguen al LHC. La figura que abre esta entrada también ha sido elegida por Philip Gibbs para comentar esta noticia en “Another record luminosity at LHC,” viXra log, August 7, 2010.

Y ya que estamos hablando del LHC, un colisionador de hadrones, no me resisto a poneros la siguiente ilustración de la diferencia entre una colisión entre dos hadrones (protones o antiprotones) y dos leptones (electrones o muones). En una colisión protón-protón a 7 TeV colisionan unas 50 partículas contra otras 50 partículas en dada protón. Además, cada haz lleva paquetes de muchos protones. El resultado es que las colisiones son bastante “sucias” comparadas con lo que sería una colisión “limpia” entre dos leptones, en la que solo colisionan una partícula contra otra.

Aquí tenéis una representación clásica de un protón. Un saco de tres quarks de valencia (las bolas azules solitarias) junto a muchos gluones (líneas a garabatos) y pares quark-antiquark (pares de bolas azul-verde). Un protón es un objeto muy complicado. En las colisiones en el LHC del CERN entre dos protones lo que en realidad se observan son colisiones quark contra quark, quark contra antiquark, gluón contra quark, y gluón contra gluón. Los diagramas de Feynman de esta figura ilustran todas estas posibilidades.

Ya lo hemos contado en varias ocasiones en este blog, pero a veces hay que repetirlo. ¿Cómo se mide el número de colisiones por segundo en un colisionador? Yo he utilizado las unidades 1/fb y 1/pb ¿qué significan? La probabilidad para un modo de colisión/desintegración entre partículas se denomina sección eficaz. La sección eficaz es un área o superficie y se suele medir en barn. Un barn es, más o menos el área transversal de un núcleo de uranio, en concreto 10-28 m². La luminosidad es el número de partículas por unidad de superficie y por unidad de tiempo en un haz (de partículas). ¿Unidad de superficie? Sí, porque en los detectores se mide un flujo incidente, un número de partículas por unidad de tiempo que incide en una unidad de área de detector. La luminosidad instantánea es la luminosidad pico y se mide unidades inversas de sección eficaz por unidad de tiempo. Por tanto, 1/fb/año es un inverso de femtobarn por año. La luminosidad integrada o acumulada es la integral (suma) de la luminosidad instantánea y se mide en unidades inversas de sección eficaz. Por tanto, 1/fb de colisiones se obtiene tras 1 año de colisiones a 1/fb/año, donde 1 pb (picobarn) = 10-12 barn, 1 nb (naoobarn) = 10-9 barn, y 1 fb (femtobarn) = 10-12 barn. Aproximadamente, en el LHC 0’1/fb son mil millones de colisiones. El objetivo para el LHC durante el bienio 2010-2011 es obtener unos diez mil millones de colisiones protón-protón con una energía en el centro de masas de 7 TeV (teraelectrónvoltio).

PS: Los dos detectores principales del LHC, tanto ATLAS como CMS, ya tienen un inverso de picobarn de colisiones almacenadas en disco. Pronto empezaremos a leer resultados interesantes de estos datos. Como nos recuerdan en “His First Inverse Picobarn,” Resonaances, 9 August 2010, un 1/pb en el LHC a 7 TeV c.m. equivale a producir (que no es lo mismo que detectar) 200000 bosones W, 60000 bosones Z, 1000 pares de quarks top, y entre 10-20 bosones de Higgs bosons (para una masa de unos 120 GeV/c²).

PS: Muy buena entrada sobre el estado actual y el futuro cercano del LHC en Philip Gibbs, “LHC Progress and Plans for August and Beyond,” viXra log, August 9, 2010. Agosto será un mes crítico (la energía en los imanes ronda el millón de julios y valor “peligroso” para la máquina). Este mes se dedicará entero a colisiones y a aprender a manejar la máquina a 25 paquetes de protones por haz. Se espera que en agosto se obtenga un segundo inverso de picobarn de colisiones. Buenas noticias para los que buscan nueva física escondidado en los datos del LHC.