Könnte dies ein NP-Complete-Problem sein?

10

Betrachten Sie die folgende Problemstellung:

Bei einer Anfangszahl ziehen Sie und Ihr Freund abwechselnd ein perfektes Quadrat davon ab. Der erste, der auf Null kommt, gewinnt. Zum Beispiel:

Ausgangszustand: 37

Spieler1 subtrahiert 16. Status: 21

Spieler2 subtrahiert 8. Status: 13

Spieler1 subtrahiert 4. Status: 9

Spieler2 subtrahiert 9. Status: 0

Spieler2 gewinnt!

Schreiben Sie ein Programm, das bei einem Anfangszustand einen optimalen Zug zurückgibt, dh einen, der garantiert zum Gewinn des Spiels führt. Wenn kein möglicher Zug Sie in einen Gewinnzustand führen kann, geben Sie -1 zurück.

Dieses Problem kann in pseudopolynomialer Zeit durch dynamische Programmierung gelöst werden . Die Idee ist nur, ein Array der Länge n (wobei n der Anfangszustand ist) von unten nach oben mit den optimalen Zügen zu füllen , oder -1, wenn kein Zug zum Gewinnen führt. Dies würde O (n * sqrt (n)) erfordern, da wir für jede Zahl in Betracht ziehen müssen, jedes mögliche perfekte Quadrat zu subtrahieren, das kleiner als es ist (es gibt ~ sqrt (n) von ihnen). Dies ist jedoch eine pseudopolynomielle Laufzeitkomplexität, da die Laufzeit tatsächlich exponentiell in Bezug auf die Größe der Eingabe in Binärform skaliert (Anzahl der zur Darstellung der Zahl verwendeten Bits).

Kann sich jemand einen Polynomalgorithmus zur Lösung dieses Problems vorstellen? Wenn nicht, könnte es NP-Complete sein? Warum?

complexity-theory time-complexity np-complete dynamic-programming pseudo-polynomial Martin Copes
quelle
1
Warum fragst du aus Neugier speziell, ob es NP-vollständig ist? (Persönlich hätte ich vermutet, dass es nicht einmal in NP ist, obwohl ich es wirklich nicht weiß.)
Ruakh
@ruakh Ich bin kürzlich während eines Codierungsinterviews auf dieses Problem gestoßen und habe die von mir beschriebene Pseudo-Polynom-Lösung mit dynamischer Programmierung vorgeschlagen. Nachdem ich mir das Problem genau überlegt hatte, konnte ich keinen polynomiellen Zeitalgorithmus finden. Ich begann mich bald zu fragen, ob dies tatsächlich kein NP-Problem (-Complete) war.
Martin Copes
Haben Sie versucht zu berechnen, welche Positionen Gewinnpositionen sind und welche Positionen verlieren? Vielleicht entsteht ein Muster.
Yuval Filmus
@ YuvalFilmus Laut Wikipedia gibt es keine bekannte Formel für dieses Muster (Sequenz A030193 in der OEIS)
Martin Copes
Richtig, ich wollte gerade eine Antwort mit diesen Informationen posten. Siehe auch A224839.
Yuval Filmus

Antworten:

6

Die Reihenfolge der Positionsverluste finden Sie im OEIS, A030193 , ebenso wie die Reihenfolge der Positionen mit dem Grundy-Wert 1, A224839 . Die Enzyklopädie zitiert mehrere relevante Artikel. Vielleicht diskutieren einige von ihnen nicht triviale Algorithmen zur Berechnung der Sequenz.

Yuval Filmus
quelle
Wie Sie bereits erwähnt haben, repräsentiert diese Sequenz die verlorenen Positionen. Selbst wenn Sie in konstanter Zeit überprüfen könnten, ob eine Position verliert oder nicht (was schwierig erscheint!), Fordert Sie das Problem dennoch auf, den optimalen Zug zurückzugeben, dh welches Quadrat Sie zum aktuellen Status subtrahieren müssten, um zu gelangen eine verlorene Position. Das Problem würde sich darauf beschränken, eine Verlustposition zu finden, indem Quadrate vom aktuellen Zustand abgezogen werden. Sie müssen also immer noch alle Quadrate durchlaufen, die kleiner als der Status sind, auch wenn Sie überprüfen können, ob eine Position in konstanter Zeit verliert.
Martin Copes
3
Richtig, es wird nicht genug sein, aber es wird ein guter Anfang sein. Vielleicht gewinnen Sie einen Einblick, wenn Sie nur den Gewinnstatus einer Position berechnen können. Außerdem reicht es aus, zu zeigen, dass es schwierig ist zu entscheiden, welche Position verliert, um zu zeigen, dass Ihr Problem in jeder vernünftigen Entscheidungsversion NP-schwer ist.
Yuval Filmus