Re: [問題] NP problem& P problem?怎麼區分?

[flashstar (閃亮的星)]

※ 引述《aether982 (阿青是我是阿青)》之銘言：
: ※ 引述《dynamicy (小人物)》之銘言：
: : 不是很懂這個怎麼區分?...
: : 可以麻煩那位解說一下,感謝!
: P denotes the class of all problems that can be
: solved by deterministic algorithms in polynomial
: time.
: NP denotes the class of all problems that can be
: solved by nondeterministic algorithms in polynomial
: time.
: A nondeterministic algorithm, when faced with a
: choice of several options, has the power to guess
: the right one (if there is any).
: We will focus on decision problems, whose answer
: is either yes or no.
: 演算法上課的講義

 在這邊NP寫的有點不清楚, 應該是要說, 像找Hamiton Cycle, 大家都知道這是一個
 NP的問題, 意思是找Hamiton Cycle沒有明確的方法,
 但要驗證找出來的path是否為Hamiton Cycle則很容易,
 這在演算法中是可以reduce到SAT的問題, 而SAT則是簡單的sum of product邏輯,
 故可以在polynomail time 去 verify出true or false.

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.224.77.77
推 aether982:謝謝你 我會去跟老師反應一下 ^^
→ flashstar:不客氣...因為今年剛考完研究所, 還蠻熟的@@"