Hay muchas pruebas que demuestran que juegos como Lemmings, Sudoku o Tetris son difíciles NP (versiones generalizadas de esos juegos, por supuesto). Las pruebas, según recuerdo, no son difíciles pero tampoco sencillas.
Deseo dar a mis estudiantes una pregunta en su tarea que aborde algún juego conocido o algo similar, por lo que estoy interesado en ejemplos a tal problema para el cual la prueba de dureza no es difícil (al menos, el estudiante puede resolverlo con alguna dirección).
Puedo recomendar el libro Puzzles, juegos y cálculos por Erik Demaine y Robert Hearn. Contiene muchos resultados. La mayoría se obtienen expresando juegos como el Sokoban en el modelo lógico de restricción de costes no determinista (NCL) . Este modelo de computación es equivalente a una máquina de Turing de espacio limitado. Dado que NCL es PSPACE-completo, basta con modelar NCL con los juegos. Esto da lugar a artilugios no tan complicados.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
