Rango Finito

fotoscódigoobservatorioshermanocerdo temas juegos

algoritmos

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.

Escalafón

Problema (muy probablemente con nombre, apellido y soluciones conocidas y optimizadas): dada una base de datos (suficientemente extensa) de jugadores de un cierto juego (imaginen Tetris) que recopila su historial ordenado de puntajes, cómo decidir, a partir de la información en la base de datos y sin tomar en cuenta las particularidades del juego, quién es el mejor jugador. Una solución burda es simplemente elegir a aquel que obtuvo el puntaje más alto. Otra es elegir a quien tiene el promedio más alto. Estas soluciones no son satisfactorias: un jugador puede obtener un puntaje elevado por simple suerte pero ser regular en general y otro puede tener un promedio superior que otro sólo porque ha jugado un juego mientras el otro ha jugado cien. Tal vez, antes de proponer una solución, debería aclararse cuáles serían las condiciones de una solución satisfactoria. Una posible condición es que la solución diferencie a los jugadores tanto como sea posible, i.e., si el historial del jugador A y el historial del jugador B son distintos, (casi) siempre debería ser capaz de decidir si A o B es mejor. En el fondo, obviamente, la pregunta es cómo definir ser mejor dada la información disponible. Recibo ideas, sugerencias, referencias, extensiones, críticas, dudas, increpaciones gratuitas y demás en los comentarios. Es para un amigo.