Komplexität der Türme von Hanoi

Ich bin auf die folgenden Zweifel in Bezug auf die Komplexität der Türme von Hanoi gestoßen , zu denen ich Ihre Kommentare haben möchte.

Ist es in NP? Versuchte Antwort: Angenommen, Peggy (Prüferin) löst das Problem und übermittelt es an Victor (Prüfer). Victor kann leicht erkennen, dass der endgültige Zustand der Lösung richtig ist (in linearer Zeit), aber er hat keine andere Wahl, als jeden von Peggys Zügen durchzugehen, um sicherzustellen, dass sie keinen illegalen Zug gemacht hat. Da Peggy mindestens 2 ^ | Scheiben | machen muss - 1 Züge (nachweisbar), auch Victor muss nachziehen. Somit hat Victor keine polynomielle Zeitüberprüfung (die Definition von NP) und kann daher nicht in NP sein.
Ist es in PSPACE ? Scheint so, aber ich kann mir nicht vorstellen, wie ich die obigen Überlegungen erweitern kann.
Ist es PSPACE-vollständig? Scheint nicht, aber ich habe nur eine vage Idee. Die automatisierte Planung, für die ToH eine bestimmte Instanz ist, ist PSPACE-vollständig. Ich denke, dass Planning weitaus schwierigere Instanzen als ToH hat.

Aktualisiert : Input = , die Anzahl der Festplatten; Ausgabe = Festplattenkonfiguration bei jedem Schritt. Nach dem Update wurde mir klar, dass dieses Eingabe- / Ausgabeformat nicht zu einem Entscheidungsproblem passt. Ich bin mir nicht sicher, welche Formalisierung geeignet ist, um die Begriffe NP, PSPACE usw. für diese Art von Problem zu erfassen. $n$

Update Nr. 2 : Nach den Kommentaren von Kaveh und Jeff bin ich gezwungen, das Problem zu präzisieren:

Die Eingabe sei das Paar von Ints wobei die Anzahl der Platten ist. Wenn die Reihenfolge der von den Datenträgern ausgeführten Bewegungen im Format (Datenträgernummer, Von-Stange, Bis-Stange) (Datenträgernummer, Von-Stange, Bis-Stange) ... von der ersten Bewegung bis zur nächsten aufgezeichnet ist last gibt das te Bit aus und ist binär codiert . $(n,i)$ $n$ $i$

Lassen Sie mich wissen, ob ich die Codierung genauer beschreiben muss. Ich nehme an, dass Kavehs Kommentar in diesem Fall zutrifft.

complexity-theory time-complexity PKG
quelle

Können Sie bitte das Towers of Hanoi-Problem definieren oder einen Link zu einer Definition erstellen?

Kaveh

PKG, ich weiß was es ist der Turm von Hanoi. Ich meinte, was ist das Rechenproblem, dass Sie seine Komplexität wissen wollen? Was ist der Input? Was ist die Ausgabe?

Kaveh

@ Kaveh: Ihre Absicht war aus Ihrem ersten Kommentar

PKG

Es tut uns leid. Übrigens gibt es Funktionskomplexitätsklassen, die normalerweise ein F vor oder nach dem Namen haben. Überprüfen Sie den Komplexitätszoo auf Definitionen.

Kaveh

Ist die Ganzzahl auch Teil der Eingabe?

i

$i$

JeffE

Antworten:

Nein, das von Ihnen beschriebene Problem ist eigentlich ganz einfach. Der Grund auf hoher Ebene ist, dass der Index ungefähr Bits lang ist, so dass wir es uns tatsächlich leisten können, Zeitpolynom in zu verbringen . $i$ $n$ $n$

Betrachten Sie das folgende verwandte Problem: Beschreiben Sie bei zwei Ganzzahlen und den ten Zug in der Lösung des Disk-Puzzles. Die Eingabegröße ist , aber tatsächlich ist nur das niedrigstwertige Bit von Bedeutung . Selbst wenn signifikant kleiner als , können wir dieses Problem im Zeitpolynom in lösen . $n$ $k$ $k$ $n$ $\lg n + \lg k < n + \lg k$ $n$ $\lg k$ $n$ $O(\log k)$

Angenommen, die Datenträger sind in aufsteigender Reihenfolge nach Größe von bis beliebig nummeriert , und die Stifte sind mit 0 = Quelle, 1 = Ziel und 2 = Reserve nummeriert. Schreiben wir für einige ganze Zahlen und . Dann auf Abbiegung : $0$ $k = (2p+1)\cdot 2^d$ $p$ $d$ $k$

Wenn ungerade ist, bewegt sich die Platte von peg zu peg . $d+n$ $d$ $(p\bmod 3)$ $((p+1)\bmod 3)$
Wenn ist, verschiebt sich die Platte peg zu peg . $d+n$ $d$ $(-p\bmod 3)$ $((-p-1)\bmod 3)$

Wir können und in der Zeit leicht berechnen, indem wir die Binärdarstellung von vom niedrigstwertigen Bit aufwärts durchlaufen . Das ist es. $p$ $d$ $O(\log k)$ $k$

Angenommen, Sie möchten wirklich das te Bit in der Ausgabesequenz, wobei Teil der Eingabe anstelle von . Wenn jede Umdrehung mit der gleichen Anzahl von Bits codiert wird - insbesondere mit Bits für die Plattennummer, Bits für den Von-Peg und Bits für den Bis-Peg - müssen wir nur rechnen die te Bewegung, wobei , und extrahieren Sie dann das entsprechende Bit. (Beachten Sie, dass in der Eingabegröße linear ist, da wir kennen müssen , um die Ausgabe zu bestimmen.) $i$ $i$ $k$ $\lg(n+1)$ $2$ $2$ $k$ $k = \lfloor{i/(\lg(n+1)+4)\rfloor}$ $\lg(n+1)+4$ $n$

Wenn wir dagegen eine Darstellung mit variabler Länge für die Plattennummern verwenden, können wir die Verschiebungsnummer in Polynomzeit durch binäre Suche finden. Wir müssen die Gesamtzahl der Umdrehungen kennen, die erforderlich sind, um die oberen Scheiben für alle zu bewegen , aber dies ist gegeben durch die Wiederholung die wir durch dynamische Programmierung in Polynomzeit auswerten können. Die restlichen Details bleiben als langweilige Übung für den Leser. $k$ $m$ $m\le k$

M (m) = 2 M (m - 1) + (\#bits to record moving disk m)

$M(m) = 2M(m-1) + (\text{\#bits to record moving disk } m)$

(Ich gehe davon aus, dass ich mindestens einen Fehler nach dem anderen oder einen Paritätsfehler gemacht habe, aber hoffentlich ist die Hauptidee klar.)

JeffE
quelle