Este poderia ser um problema NP-Complete?

10

Considere a seguinte declaração do problema:

Dado um número inicial, você e seu amigo se revezam para subtrair um quadrado perfeito dele. O primeiro a chegar a zero vitórias. Por exemplo:

Estado inicial: 37

Jogador1 subtrai 16. Estado: 21

Jogador2 subtrai 8. Estado: 13

Jogador1 subtrai 4. Estado: 9

Jogador2 subtrai 9. Estado: 0

Jogador2 vence!

Escreva um programa que, dado um estado inicial, retorne uma jogada ideal, ou seja, um que garanta a vitória no jogo. Se nenhuma jogada possível puder levá-lo a um estado vencedor, retorne -1.

Esse problema pode ser resolvido em tempo pseudo-polinomial usando programação dinâmica. A idéia é apenas preencher uma matriz de comprimento n (onde n é o estado inicial) de baixo para cima com os movimentos ideais, ou -1 se nenhum movimento levar à vitória. Isso levaria O (n * sqrt (n)), já que para cada número precisamos subtrair cada quadrado perfeito possível menor que ele (existem ~ sqrt (n) deles). No entanto, essa é uma complexidade de tempo de execução pseudo-polinomial, pois o tempo de execução é escalonado exponencialmente em relação ao tamanho da entrada em binário (número de bits usado para representar o número).

Alguém pode pensar em um algoritmo polinomial para resolver esse problema? Caso contrário, poderia ser NP-Complete? Por quê?

complexity-theory time-complexity np-complete dynamic-programming pseudo-polynomial Martin Copes
fonte
11
Por curiosidade, por que você está perguntando especificamente se é NP-completo? (Pessoalmente, eu teria imaginado que não é nem mesmo no NP, embora eu realmente não sei.)
ruach
@ruakh Encontrei recentemente esse problema durante uma entrevista de codificação e propus a solução pseudo-polinomial usando a programação dinâmica que descrevi. No entanto, depois de pensar cuidadosamente sobre o problema, não consegui criar um algoritmo de tempo polinomial. Logo comecei a me questionar se isso não era de fato um problema de NP (-Completo).
Martin Copes
Você já tentou calcular quais posições estão ganhando e quais estão perdendo? Talvez um padrão surja.
Yuval Filmus
@YuvalFilmus De acordo com a Wikipedia, não existe uma fórmula conhecida para esse padrão (sequência A030193 no OEIS)
Martin Copes
Certo, eu estava indo apenas para postar uma resposta com esta informação. Veja também A224839.
Yuval Filmus

Respostas:

6

A sequência de posições perdidas pode ser encontrada no OEIS, A030193 , assim como a sequência de posições com o valor 1 Grundy , A224839 . A enciclopédia cita vários artigos relevantes. Talvez alguns deles discutam algoritmos não triviais para calcular a sequência.

Yuval Filmus
fonte
Como você mencionou, esta sequência representa as posições perdedoras. Mesmo se você fosse capaz de verificar em tempo constante se uma posição perde ou não (o que parece difícil!), O problema ainda pede que você retorne a jogada ideal, ou seja, qual quadrado você precisaria subtrair para o estado atual para chegar ao uma posição perdida. O problema se resumia a encontrar uma posição perdida subtraindo quadrados do estado atual. Portanto, você ainda precisa percorrer todos os quadrados menores que o estado, mesmo se pudesse verificar se uma posição está perdendo em tempo constante.
Martin Copes
3
Certo, não será suficiente, mas será um bom começo. Talvez você tenha alguma ideia de poder calcular apenas o status de vitória de uma posição. Além disso, mostrar que é difícil decidir qual posição está perdendo será suficiente para mostrar que seu problema, como indicado, é difícil para NP, em qualquer versão de decisão razoável.
Yuval Filmus