作者cschenptt (chen)
看板Grad-ProbAsk
標題Re: [理工] 106 交大 演算法
時間Tue Jan 1 16:59:30 2019
請問一下這題
我的疑問是S2為什麼是對的
我的理解是 NP可以在polynomial time內被“verification”（not sloves）
P才是可以被slove
Class P: class of problems that can be solved in O(n^k)
Class NP: class of problems that can be verified in O(n^k)
所以我不是很懂 為什麼這邊寫
"一定存在NP alg. 可以"slove" NP problem"
還是關鍵字不在slove 是在NP alg.
請問"np alg."是什麼？
※ 引述《TampaBayRays (光芒今年拿冠軍)》之銘言：
: https://i.imgur.com/m4kV56r.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.98
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1546333174.A.879.html
推 eggy1018: 應該是說A可以reduce 到B再被B解吧 01/01 17:11
推 FRAXIS: NP 是指 non-deterministic polynomial time 01/02 05:33
→ FRAXIS: Class NP 有兩種定義法 一種是可在 01/02 05:35
→ FRAXIS: deterministic polynomial time verify 01/02 05:35
→ FRAXIS: 另一個是可在 non-deterministic polynomial time 解 01/02 05:35