根據定義Towers of Hanoi(河內塔)不是P問題,
書上也沒把它歸在NP,
今天我有點懷疑,它是不是NP-hard,
如果不是,他是屬於啥問題?
就上網查了一下,
在http://www.cs.uidaho.edu/~karenv/cs213/cs213.useful.pages/np.html
發現以下內容:
Contrast with Infeasible Problems
Provably infeasible problems, like the Towers of Hanoi, at not known to be in the class NP.
Consider: how would you solve the Towers of Hanoi with an infinite number of processors? There does not appear to be any way to take advantage of such plenitude.
Any "solution" to Towers of Hanoi would be a sequence of instructions on how to move the disks, which would be exponentially long and so could not be verified in a polynomial number of steps.
Even guessing doesn't help. For example, guessing where each disk goes next would still require an exponential number of guesses to solve the problem. Such an algorithm would require exponential time
由於這篇文章,前半段是在講np問題的,
與Infeasible Problems對比指的就是NP問題,
因此得知Hanoi Towers屬於Infeasible Problems.
另外在網上查NP問題,
有中文網頁把它翻成Non-polynomial time problem,
比較正確應是Nondeterministic Polynomial time,
指的是在non-deterministic Turing machine上能夠在polynomial time解決的問題,
而deterministic Turing machine,指的是由一個state到下一個state只存在唯一的下一個state.
相對的non-deterministic Turing machine的下一個state並不是唯一(包含零個),
因此,P問題指的就是在deterministic Turing machine用polynomial time能解決的問題.
