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.

El castillo de arena automático

El progreso de la Humanidad lleva siglos arrastrándonos en direcciones aparentemente aleatorias, alternativamente arruinando y promoviendo sueños. Puede que no hayamos conseguido, como en las novelas de ciencia ficción, conquistar el espacio o movernos de un lado a otro en coches voladores; sin embargo, los desarrollos recientes en el campo de la impresión tridimensional podrían traer, más pronto que tarde, cambios radicales en nuestra civilización.

Bajo la marca D-Shape se encuentra Enrico Dini, presidente la compañía británica Monolite UK, Ltd. El invento de Dini no se asemeja en nada a una impresora convencional, y supone un paso cualitativo para la incipiente tecnología de impresión tridimensional: se trata de una impresora de edificios. Un cabezal inyector alimentado por una mezcla de arena y un aglutinante inorgánico va montado sobre un pórtico móvil de varios metros de ancho. Desde ahí deposita capas alternas de arena y aglutinante de 5 a 10 milímetros de grosor, controlado por un programa CAD convencional. El resultado final: construcciones de una pieza de un material similar al mármol que pueden reproducir cualquier forma imaginable, integrando en la estructura cualquier parte hueca como ventanas, tuberías, cableado y cámaras de aislamiento. El prototipo puede crear un pequeño edificio de varios metros cúbicos sin necesidad de soportes metálicos en la cuarta parte del tiempo de lo que se tardaría mediante procedimientos convencionales, a la mitad del coste y pudiendo realizar superficies curvas y vaciados impensables con las actuales técnicas. Un vídeo lo ilustrará mejor:

Dini tiene grandes planes para su máquina: según la web de información científica Physorg se están realizando pruebas en instalaciones de alto vacío para averiguar si sería factible utilizar uno de estos aparatos en la superficie lunar, bajo el paraguas del programa Aurora de la ESA. Pero otro de los sueños de Dini quizá sea aún más irrealizable que construir ciudades en la Luna: terminar la de . Si es cierto que su máquina puede reducir los plazos a una cuarta parte, el templo podría estar acabado antes de que Barcelona vuelva a celebrar unos Juegos Olímpicos.

Las manos de Bender

Lo he visto un poco tarde (lo sacó @aberron en su estupendo Fogonazos), pero no puedo resistirme: en el laboratorio Ishikawa Komuro (Universidad de Tokio) están ultimando los manipuladores robóticos del futuro. Decir que funcionan como unas manos humanas es no estar a la altura, y con la palabra “futuro” quiero decir ya. Lo que tarden en comercializarlos. El vídeo, con más detalles que el de hace un mes, impresiona:

Más información y vídeos en la web del laboratorio.