Re: [問題] NP problem& P problem?怎麼區分?
※ 引述《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
推
61.228.84.234 06/14, , 1F
61.228.84.234 06/14, 1F
→
61.224.77.77 06/14, , 2F
61.224.77.77 06/14, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 4 篇)：