Rango Finito

fotoscódigoobservatorioshermanocerdo temas plots

complejidad

Las jerarquías científicas según Noam Chomsky

Aquí (vía Sergio, que le rinde culto) Chomsky habla de inteligencia artificial:

If you take a look at the progress of science, the sciences are kind of a continuum, but they’re broken up into fields. The greatest progress is in the sciences that study the simplest systems. So take, say physics — greatest progress there. But one of the reasons is that the physicists have an advantage that no other branch of sciences has. If something gets too complicated, they hand it to someone else. […] If a molecule is too big, you give it to the chemists. The chemists, for them, if the molecule is too big or the system gets too big, you give it to the biologists. And if it gets too big for them, they give it to the psychologists, and finally it ends up in the hands of the literary critic, and so on.

Búsqueda y destrucción

Un hombre recibe una misión: encontrar a una persona con un tatuaje del Pato Donald estampado en el culo. Es un problema aparentemente difícil de resolver. En general puede tomar mucho tiempo y esfuerzo encontrar a alguien así pero, en contraposición, corroborar que el hombre cumplió su misión es sencillo: basta bajarle los pantalones al candidato.

Soldados buscan
Soldados buscan cartas entre los restos carbonizados de una oficina de correo en Dublin, 1922.

Muchos problemas de búsqueda tienen la particularidad de que, aunque parezca difícil (en términos de tiempo) encontrar lo que se desea, verificar la validez de una solución es relativamente rápido. La pregunta es si de verdad son tan difíciles de resolver como aparentan ser. No es claro. De pronto siempre existe al fondo una manera rápida de buscar.

Por ejemplo, determinar si un número es primo parece un problema de este tipo. Requiere constatar la existencia (o no) de un divisor. Encontrar un divisor, al menos siguiendo la estrategia más obvia, tarda demasiado, pero verificar que es un divisor sólo requiere dividir y revisar el residuo (esta operación puede tomar tiempo, pero no demasiado en relación a la longitud de los números involucrados). Por muchos años se sospechó que el problema de decidir si un número era primo o no debería ser rápido de resolver, pero sólo hasta hace diez fue descubierto un procedimiento que lo hace de manera rápida, concluyente y sin condiciones en los números a evaluar.

Detrás del juego de dibujar esta versión de la Mona Lisa en un sólo trazo (uniendo con líneas rectas unos puntos elegidos de antemano) se oculta el famoso problema del agente viajero, otro de esos que parecen (y probablemente sean) difíciles de resolver aunque verificar una solución sea sencillo.

Otros problemas no han tenido la misma suerte pero tampoco han tenido la suerte opuesta: no se ha podido demostrar que no existe una solución rápida. En otras palabras, no se sabe si existen problemas de búsqueda con verificación de solución rápida que sean esencialmente difíciles. A los problemas con verificación de solución rápida los llaman NP. A los problemas con solución rápida los llaman P. Otra manera de plantear la pregunta es sí todo problema NP es en realidad P o si definitivamente existen problemas NP que no son P.

Muchos algoritmos de encriptación de uso diario basan su solidez en problemas de búsqueda con verificación rápida de solución que por lo pronto parecen ser esencialmente difíciles de resolver, como la factorización de números enteros (en el caso del algoritmo RSA). Si se demostrara que todo problema NP es P, la seguridad de estos sistemas se derrumbaría (y probablemente con ella la civilización como la conocemos). La conjetura más popular, por ende, es que P≠NP. Ese es el verdadero sacramento de nuestra fe.

La ilusión de que NP no sea lo mismo que P nos protege.

Sábado (Lumet)

Se murió Sidney Lumet. Hacía unas películas que me atormentaban mucho basadas en proponer disyuntivas éticas complicadísimas y medio imposibles de resolver sin tener que reconstruir desde escombros media estructura moral propia. Para católicos apóstatas llenos de culpas, cobardías y angustias como yo eso es casi cine de terror. El heroísmo, para Lumet, exigía ser consecuente. No había grandes premios al final más allá de cierta satisfacción por haber hecho lo correcto y no haber renunciado pese a la magnitud de la amenaza. La redención era una necesidad constante y presente, no una promesa. Los riesgos del héroe eran inmensos y en más de una ocasión sucumbía, pero incluso en el fracaso el héroe era admirable por su fidelidad a sus principios. Lumet no era un director de grandes ideas sino de preocupaciones inmensas, terribles. En sus películas había que tomar decisiones dolorosas y luego vivir con ellas. Los héroes de Lumet no vencían a sus monstruos. Su valentía consistía en negarse a ignorarlos, en señalarlos, o incluso en rendirse ante ellos sin jamás perder la conciencia de que estaban ahí. Nunca hay certezas. Todo siempre puede salir peor. Renunciar a la esperanza, empero, no es una opción.

You’re beginning to believe the illusions we’re spinning here. You’re beginning to believe that the tube is reality and that your own lives are unreal. You DO whatever the tube tells you: you dress like the tube, you eat like the tube, you raise your children like the tube, you even think like the tube. This is mass madness, you maniacs. In God’s name, you people are the real thing, WE are the illusion.