Given a problem
List all steps to move n disks from rode 1 to rode 2.
I guess you are familiar with Towers of Hanoi rules. I couldn't find a proper answer for the complexity class of this problem. My first guess would be NP or even NP-hard yet the output is exponential and no matter how hard we try there's no chance to check the answer in polynomial time even on non-deterministic Turing machine. So what's the complexity class?