Menos ajedrez y m¨¢s Tetris

En su ciudad se va a celebrar un congreso de adictos al Tetris, con 400 participantes, y usted es el encargado de alojar a 100 de ellos en el hotel Uqbar (los dem¨¢s tendr¨¢n que buscarse la vida en otros hoteles). Como es sabido, el hotel Uqbar s¨®lo tiene 50 habitaciones, as¨ª que los 100 elegidos tendr¨¢n que acomodarse dos a dos. Hasta ah¨ª, bien. Pero, cuidado, porque los adictos al Tetris son a veces muy correosos, y el organizador del congreso le ha dado una amplia lista de parejas incompatibles. "Debemos intentar que todo el mundo est¨¦ contento", le dice el organizador. "Pres¨¦nteme ma?ana todas las soluciones posibles, y yo elegir¨¦ la mejor".

Usted se sienta en su despacho con aire profesional, pero veinte horas despu¨¦s se da cuenta de que algo va mal. No hay ninguna f¨®rmula simple que pueda generar el conjunto de soluciones posibles. Mejor dicho, s¨®lo hay una, y consiste en hacerlo a lo bestia: probando todas las posibles listas de 100 adictos, agrup¨¢ndolos dos a dos de todas las formas imaginables y viendo si el resultado viola la ley de incompatibilidades. Pero eso tambi¨¦n es horrible, porque el n¨²mero de posibles formas de seleccionar 100 adictos del grupo de 400 es mayor que el n¨²mero de ¨¢tomos en el Universo conocido. Maldito congreso, ?por qu¨¦ no me quedar¨ªa yo en el pueblo jugando al ajedrez?

El rompecabezas del hotel Uqbar es un ejemplo de problema NP, que se puede definir como una pregunta tal que cada respuesta tentativa es f¨¢cil de confirmar o descartar (d¨¦le una soluci¨®n concreta al organizador del congreso, y ¨¦l ver¨¢ enseguida si es v¨¢lida o no), pero que no puede resolverse de forma sistem¨¢tica en un tiempo razonable, ni siquiera con el m¨¢s potente ordenador. Un puzle sirve como met¨¢fora intuitiva de problema NP: resolverlo lleva mucho tiempo, pero comprobar si alguien lo ha resuelto no cuesta ni un segundo. Tal vez los problemas NP no existan, y no sean m¨¢s que un reflejo de la torpeza de nuestros matem¨¢ticos actuales. Si usted logra demostrar eso, o lo contrario (que los problemas NP s¨ª existen), el Instituto de Matem¨¢ticas Clay le dar¨¢ un mill¨®n de d¨®lares.

Un adicto que asegura estar rehabilitado, Erik Demaine, del Massachusetts Institute of Technology (MIT), ha demostrado que el Tetris es un problema NP. Esto quiere decir que no hay forma de programar un ordenador para que juegue al Tetris de manera r¨¢pida y eficaz, como un jugador humano experto. El ¨²nico programa posible ser¨ªa el de la fuerza bruta: en cada momento, considerar todas las posibles piezas que pueden caer desde arriba, y evaluarlas en todas las posiciones, rotaciones y combinaciones imaginables hasta decidir cu¨¢l es la mejor. Eso lleva tanto tiempo que no es viable.

Que el Tetris sea un problema NP tambi¨¦n implica que los jugadores humanos, por muy expertos que sean, tienen que jugar cada vez de verdad, sin posibilidad de aplicar estrategias simples y generales de probada eficacia. ?sta es la raz¨®n de que genere adicci¨®n. "Cuando juegas al Tetris, est¨¢s resolviendo problemas realmente duros", explica Demaine. "El juego es horriblemente adictivo porque supone un gran desaf¨ªo intelectual".

Peores tiempos corren para el ajedrez. Michael Atherton, Xiangchuan Chen y sus colegas han analizado a varios jugadores de ajedrez mediante resonancia magn¨¦tica, una t¨¦cnica que permite ver qu¨¦ circuitos cerebrales se activan mientras el jugador est¨¢ planeando su siguiente jugada (Cognitive Brain Research, marzo de 2003). El resultado es francamente embarazoso: all¨ª se activan ¨¢reas cerebrales relacionadas con la atenci¨®n, la percepci¨®n espacial y la rotaci¨®n mental de objetos, pero las implicadas en el an¨¢lisis inteligente de problemas, situadas en el l¨®bulo frontal, parecen estar durmiendo el sue?o de los justos. Jaque mate, troncos. ?Hay por ah¨ª alg¨²n ajedrecista que quiera echar una partida de Tetris?