Juegos, rompecabezas y computación es un libro sobre la complejidad de los juegos , escrito por Robert Hearne y Erik Demaine , y publicado en 2009 por AK Peters . Está revisado de la tesis doctoral de Hearne, que fue supervisada por Demaine. [1] [2] El Comité de Lista de Bibliotecas Básicas de la Asociación de Matemáticas de América ha recomendado su inclusión en bibliotecas de matemáticas de pregrado. [3]
Juegos, acertijos y computación se refiere a la teoría de la complejidad computacional de resolver acertijos lógicos y tomar decisiones óptimas en juegos combinatorios de dos y múltiples jugadores . Su enfoque está en los 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 rompecabezas y juegos como el sudoku , Rush Hour , reversi y ajedrez (en formas generalizadas con tableros arbitrariamente grandes) sean computacionalmente difíciles: el sudoku es NP-completo , Rush Hour y reversi son PSPACE -completo, y el ajedrez es EXPTIME-complete . Más allá de probar nuevos resultados a lo largo de estas líneas, el libro tiene como objetivo proporcionar un marco unificador para probar tales resultados, mediante el uso de la lógica de restricción no determinista , un problema combinatorio abstracto que se parece más al juego que los problemas más clásicos utilizados anteriormente para las pruebas de integridad . [1] [3]
Está dividido en tres partes. La primera parte se refiere a la lógica de restricción, [3] [4] que implica la asignación de orientaciones a los bordes de un gráfico no dirigido para 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 dureza de varios juegos y acertijos del mundo real, [3] [4] mostrando que, en cada caso, los vértices y los bordes de una restricción La instancia lógica puede ser codificada por los movimientos y piezas del juego. Algunas de estas pruebas de dureza simplifican las pruebas conocidas anteriormente; unos diez de ellos son nuevos, 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 conocidos de dureza 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 lectores que no estén familiarizados con esta área. [3]
Aunque principalmente es una monografía de investigación y un trabajo 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 Juegos, rompecabezas y computación 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 algo más crítico, escribe que el libro se siente 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 cubrir. lectura de tapa. [1] Sin embargo, tanto Harkleroad como O'Rourke están de acuerdo en que el libro está bien producido y es estimulante. [1] [3]