Complexity of Towers of Hanoi

Answered By : JeffE

No, the problem you've described is actually quite easy. The high-level reason is that the index $i$ is roughly $n$ bits long, so we can actually afford to spend time polynomial in $n$.

Consider the following related problem: Given two integers $n$ and $k$, describe the $k$th move in the solution of the $n$-disk puzzle. The input size is $\lg n + \lg k < n + \lg k$, but in fact, only the least significant bit of $n$ matters. So even if $\lg k$ is significantly smaller than $n$, we can solve this problem in time polynomial in $O(\log k)$.

Suppose the disks are numbered from $0$ to whatever in increasing order by size, and pegs are numbered 0=source, 1=destination, and 2=spare. Let us write $k = (2p+1)\cdot 2^d$ for some integers $p$ and $d$. Then on turn $k$:

• If $d+n$ is odd, then disk $d$ moves from peg $(p\bmod 3)$ to peg $((p+1)\bmod 3)$.
• If $d+n$ is even, then disk $d$ moves form peg $(-p\bmod 3)$ to peg $((-p-1)\bmod 3)$.

We can easily compute $p$ and $d$ in time $O(\log k)$ by looping through the binary representation of $k$ from the least significant bit upward. That's it.

Now suppose you really want the $i$th bit in the output sequence, where $i$ is part of the input instead of $k$. If every turn is encoded using the same number of bits — specifically, $\lg(n+1)$ bits for the disk number, $2$ bits for the from-peg, and $2$ bits for the to-peg — then we just have to compute the $k$th move, where $k = \lfloor{i/(\lg(n+1)+4)\rfloor}$, and then extract the appropriate bit. (Notice that $\lg(n+1)+4$ is linear in the input size, since we need to know $n$ to determine the output.)

On the other hand, if we're using a variable-length representation for the disk numbers, then we can find the move number $k$ in polynomial time by binary search. We need to know the total number of turns needed to move the top $m$ disks, for all $m\le k$, but this is given by the recurrence $$ M(m) = 2M(m-1) + (\text{\#bits to record moving disk } m) $$ which we can evaluate in polynomial time by dynamic programming. The remaining details are left as a boring exercise for the reader.

(I assume I've made at least one off-by-one or parity error, but hopefully the main idea is clear.)

Problem Detail: 

I ran into the following doubts on the complexity of Towers of Hanoi, on which I would like your comments.

• Is it in NP? Attempted answer: Suppose Peggy (prover) solves the problem & submits it to Victor (verifier). Victor can easily see that the final state of the solution is right (in linear time) but he'll have no option but to go through each of Peggy's moves to make sure she didn't make an illegal move. Since Peggy has to make a minimum of 2^|disks| - 1 moves (provable), Victor too has to follow suit. Thus Victor has no polynomial time verification (the definition of NP), and hence can't be in NP.

• Is it in PSPACE ? Seems so, but I can't think of how to extend the above reasoning.

• Is it PSPACE-complete? Seems not, but I have only a vague idea. Automated Planning , of which ToH is a specific instance, is PSPACE-complete. I think that Planning has far more hard instances than ToH.

Updated : Input = $n$, the number of disks; Output = disk configuration at each step. After updating this, I realized that this input/output format doesn't fit a decision problem. I'm not sure about the right formalization to capture the notions of NP,PSPACE, etc. for this kind of problem.

Update #2 : After Kaveh's and Jeff's comments, I'm forced to make the problem more precise:

Let the input be the pair of ints $(n,i)$ where $n$ is the number of disks. If the sequence of moves taken by the disks is written down in the format (disk-number,from-peg,to-peg)(disk-number, from-peg, to-peg)... from the first move to the last, and encoded in binary, output the $i$th bit.

Let me know if I need to be more specific about the encoding. I suppose Kaveh's comment applies in this case?

Asked By : PKG

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/999