Games, Puzzles, and Computation es un libro sobre la complejidad de los juegos , escrito por Robert Hearn y Erik Demaine , y publicado en 2009 por AK Peters . Es una revisión de la tesis doctoral de Hearn, que fue supervisada por Demaine. [1] [2] El Comité de la Lista Básica de Bibliotecas de la Asociación Matemática de Estados Unidos lo ha recomendado para su inclusión en las bibliotecas de matemáticas de pregrado. [3]
Games, Puzzles, and Computation se ocupa de la teoría de la complejidad computacional para resolver acertijos lógicos y tomar decisiones óptimas en juegos combinatorios de dos jugadores y de varios jugadores . Se centra en juegos y acertijos que se han visto en el mundo real, en lugar de los que se han inventado con un propósito puramente matemático. [2] En esta área, es común que los acertijos y juegos como sudoku , Rush Hour , reversi y ajedrez (en formas generalizadas con tableros arbitrariamente grandes) sean computacionalmente difíciles: sudoku es NP-completo , Rush Hour y reversi son PSPACE-completos y ajedrez es EXPTIME-completo . Más allá de probar nuevos resultados en esta línea, el libro tiene como objetivo proporcionar un marco unificador para probar tales resultados, mediante el uso de lógica de restricciones no determinista , un problema combinatorio abstracto que se asemeja más al juego que los problemas más clásicos utilizados anteriormente para pruebas de completitud . [1] [3]
Se divide en tres partes. La primera parte trata de la lógica de restricciones, [3] [4] que implica asignar orientaciones a los bordes de un grafo no dirigido de modo que cada vértice tenga bordes entrantes con un peso total suficientemente grande. [1] [3] La segunda parte de este libro aplica la lógica de restricciones en nuevas pruebas de dificultad de varios juegos y rompecabezas del mundo real, [3] [4] al mostrar que, en cada caso, los vértices y los bordes de una instancia de lógica de restricciones pueden codificarse por los movimientos y las piezas del juego. Algunas de estas pruebas de dificultad simplifican pruebas previamente conocidas; unas diez de ellas son nuevas, incluido el descubrimiento de que el juego óptimo en ciertos juegos multijugador puede ser un problema indecidible . [1] Una tercera parte del libro proporciona un compendio de resultados de dificultad conocidos en la complejidad del juego, [3] [4] actualizando una lista mucho más corta de problemas completos en la complejidad del juego del libro de 1979 Computers and Intractability . Un apéndice proporciona una revisión de los métodos de la teoría de la complejidad computacional necesarios en este estudio, para los lectores no familiarizados con esta área. [3]
Aunque se trata principalmente de una monografía de investigación y una obra de referencia para investigadores en esta área, el crítico Oswin Aichholzer recomienda el libro de manera más general a cualquier persona interesada en las matemáticas de los juegos y su complejidad. [2] Liljana Babinkostova escribe que Games, Puzzles, and Computation es una lectura agradable, exitosa en su "propósito de construir un puente entre los juegos y la teoría de la computación". [4]
Leon Harkleroad es un poco más crítico, escribiendo que el libro parece acolchado en algunos lugares, [3] y Joseph O'Rourke se queja de que su organización, con muchas páginas de matemáticas abstractas antes de llegar a los juegos del mundo real, no se presta a una lectura de principio a fin. [1] Sin embargo, tanto Harkleroad como O'Rourke están de acuerdo en que el libro está bien producido y es estimulante. [1] [3]