¿Podría ser este un problema NP-Complete?

10

Considere la siguiente declaración del problema:

Dado un número inicial, usted y su amigo se turnan para restarle un cuadrado perfecto. El primero en llegar a cero gana. Por ejemplo:

Estado inicial: 37

El jugador1 resta 16. Estado: 21

El jugador2 resta 8. Estado: 13

El jugador1 resta 4. Estado: 9

El jugador2 resta 9. Estado: 0

¡Player2 gana!

Escriba un programa que, dado un estado inicial, devuelva un movimiento óptimo, es decir, uno que garantice conducir a ganar el juego. Si ningún movimiento posible puede llevarlo a un estado ganador, devuelva -1.

Este problema se puede resolver en tiempo pseudo-polinomial usando programación dinámica. La idea es simplemente llenar una matriz de longitud n (donde n es el estado inicial) de abajo hacia arriba con los movimientos óptimos, o -1 si ningún movimiento lleva a ganar. Esto tomaría O (n * sqrt (n)) ya que para cada número debemos considerar restar cada posible cuadrado perfecto más pequeño que él (hay ~ sqrt (n) de ellos). Sin embargo, esta es una complejidad de tiempo de ejecución pseudo-polinomial ya que el tiempo de ejecución en realidad se escala exponencialmente con relación al tamaño de la entrada en binario (# de bits utilizados para representar el número).

¿Alguien puede pensar en un algoritmo polinomial para resolver este problema? Si no, ¿podría ser NP-Complete? ¿Por qué?

Martin Copes
fuente
1
Por curiosidad, ¿por qué preguntas específicamente si es NP-complete? (En lo personal, me hubiera imaginado que ni siquiera está en NP, aunque realmente no lo sé.)
ruakh
@ruakh Hace poco encontré este problema durante una entrevista de codificación y propuse la solución pseudo-polinomial usando la programación dinámica que describí. Sin embargo, después de pensar cuidadosamente sobre el problema, no pude encontrar un algoritmo de tiempo polinómico. Pronto comencé a preguntarme si esto no era en realidad un problema NP (-Completo).
Martin Copes
¿Has intentado calcular qué posiciones son posiciones ganadoras y cuáles son posiciones perdedoras? Quizás surja un patrón.
Yuval Filmus
@YuvalFilmus Según Wikipedia, no existe una fórmula conocida para este patrón (secuencia A030193 en el OEIS)
Martin Copes
Bien, solo iba a publicar una respuesta con esta información. Ver también A224839.
Yuval Filmus

Respuestas:

6

La secuencia de posiciones perdedoras se puede encontrar en el OEIS, A030193 , al igual que la secuencia de posiciones que tienen el valor 1 de Grundy , A224839 . La enciclopedia cita varios artículos relevantes. Quizás algunos de ellos discuten algoritmos no triviales para calcular la secuencia.

Yuval Filmus
fuente
Como mencionó, esta secuencia representa las posiciones perdedoras. Incluso si pudieras comprobar en tiempo constante si una posición pierde o no (¡lo que parece difícil!), El problema aún te pide que devuelvas el movimiento óptimo, es decir, qué cuadrado necesitarías restar al estado actual para llegar a Una posición perdedora. El problema se reduciría a encontrar una posición perdedora restando cuadrados del estado actual. Por lo tanto, aún debe recorrer todos los cuadrados más pequeños que el estado, incluso si puede verificar si una posición está perdiendo en el tiempo constante.
Martin Copes
3
Bien, no será suficiente, pero será un buen comienzo. Tal vez obtendrá una idea de poder calcular solo el estado ganador de una posición. Además, demostrar que es difícil decidir qué posición está perdiendo será suficiente para demostrar que su problema, como se indicó, es NP-difícil, en cualquier versión de decisión razonable.
Yuval Filmus