Algorithme de temps polynomial non déterministe par rapport au certificat / vérificateur pour montrer de l'adhésion à NP

Question

Dans cet article ( https://arxiv.org/pdf/1706.06708.pdf ) Les auteurs prouvent qu'une résolution de manière optimale la $ N \ TIMES N \ TIMES N € / SPAN> Rubik's Cube est un problème complet. Dans le processus, ils doivent montrer que le problème de décision pertinent appartient au NP (section 2.5 à la page 6). Pour ce faire, ils décrivent un algorithme qui résout de manière non déterminante le cube en temps polynomial. Il me semble que c'est plus d'efforts que nécessaire.

En particulier, le problème de décision pertinent est le suivant: le problème du cube de Rubik a comme entrée une permutation $ t $ et une valeur $ k $ . L'objectif est de décider si $ t $ peut être résolu dans $ k $ ou moins de mouvements. Donc, plutôt que de construire un algorithme de solution de temps polynomial de polynôme non déterministe, ils pourraient simplement donner un certificat qu'une décision "oui" est juste une liste de $ k $ déplace et vérifie qui vérifie que c'est du temps polynomial.

Donc, mes questions sont les suivantes. Sont les deux définitions ci-dessous en réalité équivalentes?

1. NP est la classe de la complexité des problèmes de décision résolvables par une machine à trouble non déterministe en temps polynomial.
2. NP est la classe de la complexité des problèmes de décision pour lesquels une solution peut être confirmée en temps polynomial (déterministe)?

Et s'ils sont équivalents, pourquoi les auteurs du papier lié choisiraient-ils la méthode plus difficile (ou je me trompe de cette hypothèse)?

---

Notez que je pose cette question sur plusieurs sites Web Stackexchange, car je ne suis pas sûr d'où il convient le mieux. Si c'est inapproprié ici, je vais le supprimer volontiers. De même, je vais créer un lien vers une bonne solution sur un autre site s'il est répondu là-bas.

Answer 1

Le certificat que vous proposez peut ne pas être polynomial de la taille de l'entrée.

La taille d'entrée du problème est $ o (n ^ 3 + \ log k) $ , tandis que votre certificat a la taille $ \ Omega (k \ journal n) $ .Ce n'est pas polynomial, par exemple, pour $ k= 2 ^ n $ .

Votre certificat fonctionnerait si vous le définissez, par exemple sur une liste vide chaque fois que $ k=omega (\ frac {n ^ 2} {\ journal n}) $ et modifiez le vérificateur pour vérifier simplement si la configuration d'entrée du cube est satisfable pour toute valeur de ce type de $ k $ (ignorant ainsi le certificat).