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?

  • $\begingroup$ This is not a duplicate of the linked question. The linked question asks about printing the k th move given a k and an n. This question asks about printing every move given an n. The title would benefit from more specificity but the question is different. $\endgroup$ Commented Dec 24, 2016 at 21:38
  • 1
    $\begingroup$ Related, but the precise formulation is different: cs.stackexchange.com/q/999/755 $\endgroup$
    – D.W.
    Commented Dec 25, 2016 at 6:21
  • $\begingroup$ The appropriate notion might be enumeration complexity. $\endgroup$ Commented Feb 25, 2017 at 2:50


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.