No, no la guerra contra las drogas, sino el juego de la Guerra considerada en ¿La guerra tiene una duración esperada infinita? Como se señaló en esa discusión, el juego de la guerra puede ser eterno, pero mi pregunta es: ¿se puede decidir en tiempo polinómico si una configuración dada conduce a un juego periódico o finito (la pregunta es decidible, ya que se puede simplemente mirar una secuencia de $n n!$ movimientos (donde $n$ es el número inicial de tarjetas), pero $n n!$ no es tan pequeño).
EDITAR Para responder a la muy buena pregunta de Joel: la configuración es: los dos adversarios tienen mazos $A$ y $B,$ ambos boca abajo. dan la vuelta a sus cartas superiores, las llaman $a_1$ y $b_1.$ Si $v(a_1) > v(b_1)$ ( $v()$ es el valor), ponemos $a_1$ encima de $b_1,$ dar la vuelta a la pila de dos cartas y añadirlas al fondo de $A$ (y de forma similar si $v(b_1) > v(b_k).$ Si $v(a_1) = v(b_1)$ volteamos dos cartas más $a_2, b_2$ ponerlos encima de $a_1, b_1$ respectivamente. Si $v(a_2) > v(b_2)$ ponemos la pila de $a$ s en la parte superior de la pila de $b$ s, voltear el resultado $4$ -apilado al revés, y añadirlo al fondo de la $A$ pila. Si $v(a_2) = v(b_2)$ seguimos como hasta ahora. Si seguimos obteniendo valores iguales, y uno de los jugadores se queda sin cartas, el otro jugador gana. Si ambos jugadores se quedan sin cartas simultáneamente, la partida se declara como un empate.
