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).
Editar:
La programación con beneficios y plazos es NP-Completa. La versión de decisión es algo así,
Dejemos que $A$ sea un conjunto de $n$ tareas, $\{a_1, \ldots, a_n\}$ cada uno con un tiempo de ejecución asociado, $t_i$ beneficios, $p_i$ y el plazo, $d_i$ . Sólo se puede ejecutar una tarea a la vez; si la tarea no se completa antes de su plazo asociado, no se recibe su beneficio. ¿Existe un horario que devuelva un beneficio de $k$ ?
Es relativamente fácil de mostrar, Por ejemplo , ciclo hamiltoniano $\leq_P$ programación con beneficios y plazos.
Tuve una clase de matemáticas en la que teníamos que resolver el cubo de rubiks: http://web.mit.edu/sp.268/www/rubik.pdf (esto no es de mi clase específica, pero era similar)
Sipser presenta dos problemas de este tipo en la sección de ejercicios del capítulo sobre completitud NP de su libro . El primero está inspirado en el Buscaminas, como proponía un comentario:
Dejemos que $G$ sea un grafo no dirigido, en el que cada nodo contiene una única mina oculta o está vacío. El jugador elige los nodos, uno por uno. Si el jugador elige un nodo que contiene una mina, pierde. Si el jugador elige un nodo vacío, el jugador aprende el número de nodos vecinos que contienen minas. (Un nodo vecino es uno conectado al nodo elegido por una arista). El jugador gana si y cuando todos los nodos vacíos han sido elegidos así. En el problema de consistencia de la mina se le da un gráfico $G$ junto con los números que etiquetan algunos de $G$ de los nodos. Debe determinar si es posible colocar minas en los nodos restantes, de modo que cualquier nodo $v$ que está etiquetado como $m$ tiene exactamente $m$ nodos vecinos que contienen minas. Formule este problema como un lenguaje y demuestre que es NP-completo.
El otro es un juego de solitario:
Se le da un $m \times m$ tablero. En cada uno de sus $m^2$ posiciones se encuentra una piedra azul, una piedra roja, o nada en absoluto. Se juega eliminando piedras del tablero de manera que cada columna contenga sólo piedras de un solo color y cada fila contenga al menos una piedra. Ganas si consigues este objetivo. Ganar puede o no ser posible, dependiendo de la configuración inicial. Deje que SOLITAIRE $= \{\langle G\rangle \;|\; G \mbox{ is a winnable game configuration}\}$ . Demostrar que SOLITAIRE es NP-completo.
¡¡Sokoban!! Es NP-duro y P-SPACE completo .
Un artículo reciente demuestra de forma relativamente sencilla que Super Mario Brothers es NP-completo (junto con la dureza NP de muchos otros juegos clásicos de Nintendo). Véase http://jeremykun.wordpress.com/2012/03/22/nintendo-np-hard/ para ver lo más destacado y el documento vinculado para obtener más detalles.
Su tarea puede ser que diseñen los artilugios para el juego que elijan, o que combinen los artilugios juntos para demostrar la dureza NP.
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.
