作者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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1546333174.A.879.html
1F：推 eggy1018: 应该是说A可以reduce 到B再被B解吧 01/01 17:11
2F：推 FRAXIS: NP 是指 non-deterministic polynomial time 01/02 05:33
3F：→ FRAXIS: Class NP 有两种定义法 一种是可在 01/02 05:35
4F：→ FRAXIS: deterministic polynomial time verify 01/02 05:35
5F：→ FRAXIS: 另一个是可在 non-deterministic polynomial time 解 01/02 05:35