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?