河内塔的复杂度 class
Complexity class of Towers of Hanoi
给出一个问题
Given n print every step it takes to move n disks from rode 1 to rode
2
我需要通过此特定任务确定此问题的复杂性 class。显然不在 P 中，因为很明显这个问题的复杂性是 O(2^n) 并且我们不能做得更好，因为我们必须打印指数大小的输出。我的下一个猜测是 NP 甚至 NP-hard，但我认为这不可能，因为无论算法多么聪明，即使在非行列式机器上，我们也无法在多项式时间内检查指数大小输出。那么，复杂度是多少class？
可以从一开始就确定正确的步骤，而无需通过试错搜索来做出正确的决定。因此这个问题不是decision problem, to which classes such as NP适用的。
这更像是 function problem。时间复杂度确实是由要输出的步数决定的，即2n-1，即O(2n).
相应的class因此是FEXPTIME-Complete，前缀F代表Function 和 Complete 表示它不能在小于指数时间的时间内完成（如 P）。它类似于决策问题的 EXPTIME-Complete class，即 O(2polynomial(n)).
决策问题
你的问题有一个令人困惑的方面：问题陈述是关于打印步骤的，由重申“...确定这个问题的复杂性class” .然而有些短语，你提到 "we can't check the exponential size output in polynomial time"。所以看起来你混合了两个不同的问题：
- 为给定的 n 生成（正确的）步骤列表
- 验证给定 n 和步骤列表的正确性。
第二个是一个决策问题，在那种情况下你会说它在EXPTIME-Complete class.
给出一个问题
Given n print every step it takes to move n disks from rode 1 to rode 2
我需要通过此特定任务确定此问题的复杂性 class。显然不在 P 中，因为很明显这个问题的复杂性是 O(2^n) 并且我们不能做得更好，因为我们必须打印指数大小的输出。我的下一个猜测是 NP 甚至 NP-hard，但我认为这不可能，因为无论算法多么聪明，即使在非行列式机器上，我们也无法在多项式时间内检查指数大小输出。那么，复杂度是多少class？
可以从一开始就确定正确的步骤，而无需通过试错搜索来做出正确的决定。因此这个问题不是decision problem, to which classes such as NP适用的。
这更像是 function problem。时间复杂度确实是由要输出的步数决定的，即2n-1，即O(2n).
相应的class因此是FEXPTIME-Complete，前缀F代表Function 和 Complete 表示它不能在小于指数时间的时间内完成（如 P）。它类似于决策问题的 EXPTIME-Complete class，即 O(2polynomial(n)).
决策问题
你的问题有一个令人困惑的方面：问题陈述是关于打印步骤的，由重申“...确定这个问题的复杂性class” .然而有些短语，你提到 "we can't check the exponential size output in polynomial time"。所以看起来你混合了两个不同的问题：
- 为给定的 n 生成（正确的）步骤列表
- 验证给定 n 和步骤列表的正确性。
第二个是一个决策问题，在那种情况下你会说它在EXPTIME-Complete class.