Nichtdeterministische Polynom-Zeitalgorithmus Versus-Zertifikat / Verifizierer für die Anzeige der Mitgliedschaft in NP

Question

in diesem Beitrag ( https://arxiv.org/pdf/1706.06708.pdf ) Die Autoren beweisen, dass das $ n \ times n \ times n $ optimal löst> Rubiks Cube ist ein np-vollständige Problem. Dabei müssen sie zeigen, dass das entsprechende Entscheidungsproblem in NP gehört (Abschnitt 2.5 auf Seite 6). Dazu beschreiben sie einen Algorithmus, der den Würfel in der Polynomzeit nicht löst. Es scheint mir, dass dies mehr anstrebt als nötig.

Insbesondere ist das einschlägige Entscheidungsproblem wie folgt: Das Rubik-Cube-Problem hat als Input eine Permutation $ T $ und einen Wert $ K $ . Ziel ist es, zu entscheiden, ob $ T $ in $ K $ oder weniger Bewegungen gelöst werden kann. Anstatt einen nicht deterministischen Polynom-Zeitlösungsalgorithmus zu erstellen, können sie einfach ein Zertifikat geben, dass eine Entscheidung "Ja" nur eine Liste von höchstens in den meisten $ K $ bewegt und verifiziert Diese Überprüfung ist eine Polynomzeit.

also sind meine fragen wie folgt. Sind die beiden folgenden Definitionen eigentlich gleichwertig?

.
1. nP ist die Komplexitätsklasse von Entscheidungsproblemen, die von einer nicht-ländlichen Trägermaschine in der Polynomialzeit lösbar sind.
2. np ist die Komplexitätsklasse von Entscheidungsproblemen, für die eine Lösung bei der Polynomialzeit (deterministisch) bestätigt werden kann?

und wenn sie gleichwertig sind, warum wählen die Autoren des verknüpften Papiers die schwierigere Methode (oder bin ich falsch an dieser Annahme)?

---

Beachten Sie, dass ich diese Frage auf mehreren Stackexchange-Websites veröffentlichen, da ich nicht sicher bin, wo es am besten passt. Wenn es hier unangemessen ist, lösche ich es glücklich. In ähnlicher Weise verlinke ich auf eine gute Lösung auf einer anderen Seite, wenn es dort beantwortet wird.

Answer 1

Das von Ihnen vorgeschlagene Zertifikat ist möglicherweise nicht auf Polynom in der Größe der Eingabe.

Die Eingabegröße des Problems ist $ o (n ^ 3 + \ log k) $ , während Ihr Zertifikat die Größe $ \ Omega (k \ log n) $ .Dies ist kein Polynom, z. B. für $ k= 2 ^ n $ .

Ihr Zertifikat würde funktionieren, wenn Sie es einstellen, z. B. in einer leeren Liste, wenn $ k=omga (\ frac {n ^ 2} {\ log n}) $ und ändern Sie den Verifizierer, um einfach zu überprüfen, ob die Eingabekonfiguration des Cube für einen beliebigen Wert von $ K $ lösbar ist (somit das Zertifikat ignorieren).