Complexity class of Towers of Hanoi

Question

Given a problem

Given n print every step it takes to move n disks from rode 1 to rode 2

I need to determine the complexity class of this problem with this specific task. It is clearly not in P as it is obvious that complexity of this problem is O(2^n) and we can't do better as we have to print output of exponential size. My next guess would be NP or even NP-hard but I think it can't be the case as not matter how clever the algorithm is, we can't check the exponential size output in polynomial time even on non-determinant machine. So, what's the complexity class?

Answer 1

The correct steps can be determined from the start without needing a trial-error search to make the right decision. Therefore this problem is not a decision problem, to which classes such as NP apply.

This is more of a function problem. The time complexity is indeed determined by the number of steps to be output, which is 2ⁿ-1, i.e. O(2ⁿ).

The corresponding class would thus be FEXPTIME-Complete, the prefixed F standing for Function, and Complete signifying that it cannot be done in less than exponential time (like P). It is analogous to the EXPTIME-Complete class for decision problems, i.e. O(2^{polynomial(n)}).

Decision problem

There is a confusing aspect in your question: The problem statement is about printing steps, reaffirmed by "... determine the complexity class of this problem". Yet some phrases down the line, you mention "we can't check the exponential size output in polynomial time". So it seems you mix two different problems:

1. Generating the (correct) list of steps for a given n
2. Verifying the correctness given n and a list of steps.

The second is a decision problem, and in that case you would say it is in the EXPTIME-Complete class.