Złożoność wież Hanoi

Wpadłem w następujące wątpliwości co do złożoności Towers of Hanoi , co do których chciałbym waszych komentarzy.

• Czy to jest w NP? Próba odpowiedzi: Załóżmy, że Peggy (przysłowie) rozwiązuje problem i przekazuje go Victorowi (weryfikatorowi). Victor łatwo widzi, że końcowy stan rozwiązania jest właściwy (w czasie liniowym), ale nie będzie miał innej opcji, jak przejść przez każdy ruch Peggy, aby upewnić się, że nie wykonała nielegalnego ruchu. Ponieważ Peggy musi wykonać co najmniej 2 ^ | dyski | - 1 ruchy (możliwe do udowodnienia), Victor też musi podążać za nim. Tak więc Victor nie ma wielomianowej weryfikacji czasu (definicja NP), a zatem nie może być w NP.

• Czy to jest w PSPACE ? Wydaje się, że tak, ale nie mogę wymyślić, jak rozszerzyć powyższe rozumowanie.

• Czy jest to PSPACE-complete? Nie wydaje się, ale mam tylko niejasny pomysł. Zautomatyzowane planowanie, którego szczególnym przykładem jest ToH, jest kompletne z PSPACE. Myślę, że planowanie ma znacznie więcej trudnych instancji niż ToH.

Zaktualizowano : Dane wejściowe = $n$ , liczba dysków; Dane wyjściowe = konfiguracja dysku na każdym kroku. Po zaktualizowaniu tego, zdałem sobie sprawę, że ten format wejścia / wyjścia nie pasuje do problemu decyzyjnego. Nie jestem pewien odpowiedniej formalizacji, aby uchwycić pojęcia NP, PSPACE itp. Dla tego rodzaju problemu.

Aktualizacja # 2 : Po komentarzach Kaveha i Jeffa jestem zmuszony sprecyzować problem:

Niech wejściem będzie para liczb całkowitych $(n,i)$ gdzie $n$ jest liczbą dysków. Jeśli sekwencja ruchów wykonanych przez dyski jest zapisana w formacie (numer dysku, od kołka, do kołka) (numer dysku, od kołka, do kołka) ... od pierwszego przejścia do ostatni i zakodowany w formacie binarnym, wypisuje $i$ ty bit.

Daj mi znać, jeśli będę musiał bardziej szczegółowo określić kodowanie. Przypuszczam, że komentarz Kaveha ma zastosowanie w tym przypadku?

Nie, opisany przez ciebie problem jest właściwie dość łatwy. Głównym powodem jest to, że indeks ma długość w przybliżeniu n bitów, więc możemy pozwolić sobie na spędzenie czasu wielomianu w n .$i$$n$$n$

Rozważ następujący powiązany problem: Biorąc pod uwagę dwie liczby całkowite i k , opisz k- ty ruch w rozwiązaniu zagadki n- dysk. Rozmiar wejściowy to lg n + lg k < n + lg k , ale w rzeczywistości tylko najmniej znacząca część n ma znaczenie. Więc nawet jeśli lg k jest znacznie mniejsze niż n , możemy rozwiązać ten problem w postaci wielomianu czasowego w O ( log k ) .$n$$k$$k$$n$$\lg n + \lg k < n + \lg k$$n$$\lg k$$n$$O(\log k)$

Załóżmy, że dyski są ponumerowane od do cokolwiek w kolejności rosnącej według rozmiaru, a kołki są ponumerowane 0 = źródło, 1 = miejsce docelowe i 2 = zapasowe. Napiszmy k = ( 2 p + 1 ) ⋅ 2 d dla niektórych liczb całkowitych p i d . Następnie na kolei k :$0$$k = (2p+1)\cdot 2^d$$p$$d$$k$

• Jeśli jest nieparzyste, dysk d przenosi się z kołka ( p mod 3 ) do kołka ( ( p + 1 ) mod 3 ) .$d+n$$d$$(p\bmod 3)$$((p+1)\bmod 3)$
• Jeśli jest parzyste, dysk d przenosi się z peg ( - p mod 3 ) do peg ( ( - p - 1 ) mod 3 ) .$d+n$$d$$(-p\bmod 3)$$((-p-1)\bmod 3)$

Możemy łatwo obliczyć i d w czasie O ( log k ) , zapętlając binarną reprezentację k od najmniej znaczącego bitu w górę. Otóż ​​to.$p$$d$$O(\log k)$$k$

Załóżmy teraz, że naprawdę potrzebujesz tego bitu w sekwencji wyjściowej, gdzie i jest częścią wejścia zamiast k . Jeśli każda kolej jest zakodowana przy użyciu tej samej liczby bitów - konkretnie lg ( n + 1 ) bitów dla numeru dysku, 2 bity dla pega i 2 bity dla pega - musimy po prostu obliczyć k th ruch, gdzie k = ⌊ i / ( lg ( n + 1 ) + 4 ) $i$$i$$k$$\lg(n+1)$$2$$2$$k$$k = \lfloor{i/(\lg(n+1)+4)\rfloor}$, a następnie wyodrębnij odpowiedni bit. (Zauważ, że ma wielkość wejściową liniową, ponieważ musimy znać n, aby określić wynik.)$\lg(n+1)+4$$n$

Z drugiej strony, jeśli używamy reprezentacji zmiennej długości dla numerów dysków, możemy znaleźć liczbę przesunięcia w czasie wielomianowym przez wyszukiwanie binarne. Musimy znać całkowitą liczbę zwojów potrzebną do przeniesienia górnych m dysków, dla wszystkich m ≤ k , ale jest to podane przez powtarzalność M ( m ) = 2 M ( m - 1 ) + ( \ # bitów, aby nagrać ruch dysk  m ), który możemy ocenić w czasie wielomianowym przez programowanie dynamiczne. Pozostałe szczegóły pozostawiają czytelnikowi nudne ćwiczenie.$k$$m$$m\le k$

(Zakładam, że popełniłem przynajmniej jeden błąd parzystości lub błąd parzystości, ale mam nadzieję, że główny pomysł jest jasny).