P=NP: y ahora viene cuando la matan

Tan contento que estaba yo: uno de mis autores favoritos, , liberó hace un tiempo su primera colección de historias cortas con una . Hela aquí en toda su gloria: Toast. Aún no he terminado de leerla, y ya estoy, con perdón de la mesa, cagándome por las patas abajo. Maldita realidad.

La primera historia corta de la colección, Anticuerpos, toma como escenario un tema recurrente de la literatura de Stross: una singularidad tecnológica de despegue rápido (hard takeoff singularity). En cristiano: un desarrollo técnico que facilita otros, en una cascada de aceleración imparable. El ejemplo principal (y el de esta historia corta) es una inteligencia artificial. Si entre los objetivos de esta IA está mejorar sus capacidades, puede hacerlo diseñando e implementando algoritmos más capaces y procesadores más rápidos. Sus “hijas” tardarán menos aún en superarse a sí mismas, alcanzando eventualmente algún límite máximo de capacidad de computación por metro cúbico de planeta. Y nosotros, sin haberlo visto venir. Para la segunda iteración, las IAs nos sacan la misma ventana que nosotros a los chimpancés. Para la tercera, estamos al nivel de las hormigas.

¿Y cuál es el evento que dispara los acontecimientos en Anticuerpos? Algo aparentemente sin importancia para un lego: el descubrimiento de que el tiene solución en , y por tanto que . En breve: P y NP son clases de complejidad de problemas. Un problema de tipo P puede resolverse en tiempo polinómico, lo que es aproximadamente equivalente a decir que con la suficiente potencia de cálculo podremos hallar soluciones en plazos de tiempo razonables, donde razonable es menor que antes de que se congele el infierno. Sin embargo, los problemas de sólo pueden verificarse fácilmente: algunos de ellos (los ) no tienen algoritmos que permitan su solución en tiempo polinómico. (Matemáticamente, se dice que NP contiene a P, aunque no se sabe si es una relación de contenido estricto; ambos conjuntos podrían ser iguales.)

Esta asimetría fundamental tiene multitud de usos en computación; el más relevante es la criptografía de clave pública. Multiplicar dos números primos muy grandes es algo que se hace en un momento, pero factorizar el resultado para obtener los dos números de partida puede tomar un tiempo inasumible, sin importar la potencia de proceso que se le dedique al asunto. Si resultara que P = NP, todas las comunicaciones encriptadas del mundo se irían al garete, todas las transacciones seguras dejarían de serlo y sería imposible asegurar la integridad de nada. Si por azar resultara que la inteligencia de un sistema lógico dependiera de la solución de un problema NP-completo, el haber resuelto cualquier otro en tiempo polinómico permitiría, por equivalencias matemáticas más o menos triviales, resolver éste y traer al mundo una IA con ganas de marcha. Es posible que, sin salvaguardas de un tipo muy especial (o incluso con ellas), cualquier problema difícil que se le proponga resolver a una IA derive en un ciclo imparable de apropiación de recursos y automejora. Esos recursos sean primero nuestros ordenadores, y después todos los átomos de la Tierra que puedan ponerse en disposición de computar, incluidos nuestros pobres cuerpos.

Aunque parezca increíble, todavía no os he destripado la historia. Tal vez no me dé tiempo si esto que acabo de leer resulta ser cierto: Polynomial Time Code For 3-SAT Released, P==NP (Slashdot), o su fuente original. El problema de la (y su caso particular ) es NP-completo. Si resulta tener solución en P —el autor ha publicado incluso código fuente— entonces P = NP, todos los problemas NP tienen solución fácil y nuestra economía digital se desploma sobre nuestras cabezas antes de que podamos decir…


Nota: no soy matemático y soy incapaz de determinar por mí mismo si la supuesta prueba de P = NP de la que doy noticia aquí es o no correcta. No saquéis todo vuestro dinero del banco todavía. Esperad a que yo lo haga, por favor.

Nota 2: Este artículo forma parte de la décima edición del Carnaval de Matemáticas, esta vez en casa de Francis (th)E mule Science’s News.

Adenda (28/02/2011): Parece que finalmente el autor de la supuesta pruebe de P=NP ha encontrado un error en su razonamiento. Falsa alarma.

Publicado por

Iván Rivera

Another instance of Homo sapiens.