Serait-ce un problème NP-Complete?

10

Considérez l'énoncé du problème suivant:

Étant donné un nombre initial, vous et votre ami, à tour de rôle, en soustrayez un carré parfait. Le premier à arriver à zéro gagne. Par exemple:

État initial: 37

Le joueur 1 soustrait 16. État: 21

Le joueur 2 soustrait 8. État: 13

Le joueur 1 soustrait 4. État: 9

Player2 soustrait 9. État: 0

Player2 gagne!

Écrivez un programme qui, étant donné un état initial, renvoie un coup optimal, c'est-à-dire un coup sûr qui mènera à la victoire. Si aucun mouvement possible ne peut vous mener à un état gagnant, renvoyez -1.

Ce problème peut être résolu en temps pseudo-polynomial en utilisant la programmation dynamique. L'idée consiste simplement à remplir un tableau de longueur n (où n est l'état initial) de bas en haut avec les mouvements optimaux, ou -1 si aucun mouvement ne mène à la victoire. Cela prendrait O (n * sqrt (n)) car pour chaque nombre, nous devons considérer la soustraction de chaque carré parfait possible plus petit que lui (il y en a ~ sqrt (n)). Cependant, il s'agit d'une complexité d'exécution pseudo-polynomiale, car l'exécution évolue en fait de manière exponentielle en fonction de la taille de l'entrée en binaire (nombre de bits utilisés pour représenter le nombre).

Quelqu'un peut-il penser à un algorithme polynomial pour résoudre ce problème? Sinon, pourrait-il être NP-Complete? Pourquoi?

complexity-theory time-complexity np-complete dynamic-programming pseudo-polynomial Martin Copes
la source
1
Par curiosité, pourquoi demandez-vous spécifiquement si c'est NP-complet? (Personnellement, j'aurais deviné que ce n'est même pas dans NP, même si je ne sais vraiment pas.)
ruakh
@ruakh J'ai récemment rencontré ce problème lors d'une interview de codage et j'ai proposé la solution pseudo-polynomiale utilisant la programmation dynamique que j'ai décrite. Cependant, après avoir soigneusement réfléchi au problème, je n'ai pas pu trouver d'algorithme de temps polynomial. J'ai rapidement commencé à me demander si ce n'était pas en fait un problème NP (-Complete).
Martin Copes
Avez-vous essayé de calculer les positions qui gagnent et celles qui perdent? Peut-être qu'un modèle se posera.
Yuval Filmus
@YuvalFilmus Selon Wikipedia, il n'y a pas de formule connue pour ce modèle (séquence A030193 dans l'OEIS)
Martin Copes
Bon, j'allais juste poster une réponse avec cette information. Voir aussi A224839.
Yuval Filmus

Réponses:

6

La séquence des positions perdantes peut être trouvée dans l'OEIS, A030193 , de même que la séquence des positions ayant la valeur Grundy 1, A224839 . L'encyclopédie cite plusieurs articles pertinents. Certains d'entre eux discutent peut-être d'algorithmes non triviaux pour calculer la séquence.

Yuval Filmus
la source
Comme vous l'avez mentionné, cette séquence représente les positions perdantes. Même si vous avez pu vérifier en temps constant si une position perd ou non (ce qui semble difficile!), Le problème vous demande toujours de retourner le mouvement optimal, c'est-à-dire quel carré vous devez soustraire à l'état actuel pour arriver à une position perdante. Le problème se résumerait à trouver une position perdante en soustrayant les carrés de l'état actuel. Vous devez donc toujours parcourir tous les carrés plus petits que l'état, même si vous pouvez vérifier si une position perd en temps constant.
Martin Copes du
3
Bon, ce ne sera pas suffisant, mais ce sera un bon début. Vous pourrez peut-être mieux comprendre le fait de pouvoir calculer uniquement le statut gagnant d'un poste. De plus, montrer qu'il est difficile de décider quelle position perdra sera suffisant pour montrer que votre problème comme indiqué est NP-difficile, dans toute version de décision raisonnable.
Yuval Filmus