2
$\begingroup$

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?

$\endgroup$
  • $\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$ – user34258 Dec 24 '16 at 21:38
  • 1
    $\begingroup$ Related, but the precise formulation is different: cs.stackexchange.com/q/999/755 $\endgroup$ – D.W. Dec 25 '16 at 6:21
  • $\begingroup$ The appropriate notion might be enumeration complexity. $\endgroup$ – Yuval Filmus Feb 25 '17 at 2:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.