Re: [理工] 106 交大 演算法

看板Grad-ProbAsk作者 (chen)時間7年前 (2019/01/01 16:59), 編輯推噓2(2推 0噓 3→)
留言5則, 2人參與, 7年前最新討論串2/2 (看更多)
請問一下這題 我的疑問是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
推
01/01 17:11, 7年前 , 1F
應該是說A可以reduce 到B再被B解吧
01/01 17:11, 1F
推
01/02 05:33, 7年前 , 2F
NP 是指 non-deterministic polynomial time
01/02 05:33, 2F
→
01/02 05:35, 7年前 , 3F
Class NP 有兩種定義法 一種是可在
01/02 05:35, 3F
→
01/02 05:35, 7年前 , 4F
deterministic polynomial time verify
01/02 05:35, 4F
→
01/02 05:35, 7年前 , 5F
另一個是可在 non-deterministic polynomial time 解
01/02 05:35, 5F
‣ 更多 cschenptt 的文章
文章代碼(AID): #1SAolsXv (Grad-ProbAsk)
‣ 更多 cschenptt 的文章
文章代碼(AID): #1SAolsXv (Grad-ProbAsk)