[理工] 105交大資演

看板Grad-ProbAsk作者 (沉默的EVE)時間5年前 (2019/01/04 23:44), 編輯推噓4(4推 0噓 6→)
留言10則, 3人參與, 5年前最新討論串7/10 (看更多)
https://i.imgur.com/cMhXsG8.jpg
想問一下這題各個選項t or f 跟原因 答案好像是d 謝謝～ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.82.8.135 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1546616685.A.600.html
→
01/05 00:45, 5年前 , 1F
(A)NPC 是NPH和NP的交集
01/05 00:45, 1F
推
01/05 01:23, 5年前 , 2F
(B)要先有一組certificates,並在polynomial time verify
01/05 01:23, 2F
→
01/05 01:23, 5年前 , 3F
才是NP
01/05 01:23, 3F
推
01/05 01:25, 5年前 , 4F
(C)不太確定 我覺得是NP-complete 可以互相reduce 的條
01/05 01:25, 4F
→
01/05 01:25, 5年前 , 5F
件
01/05 01:25, 5F
推
01/05 01:27, 5年前 , 6F
(E)反過來了，因為可以reduce到SAT表示SAT比較原問題難
01/05 01:27, 6F
→
01/05 01:27, 5年前 , 7F
解，此時仍沒辦法知道原問題多難，所以不能確定原問題NP
01/05 01:27, 7F
→
01/05 01:27, 5年前 , 8F
-complete, 反過來才有辦法說明～
01/05 01:27, 8F
→
01/05 01:27, 5年前 , 9F
以上有錯 還麻煩各位大大指正了
01/05 01:27, 9F
推
01/05 03:09, 5年前 , 10F
(C) NPH 可能比 NPC 難 所以不一定可以 reduce
01/05 03:09, 10F
‣ 更多 silenteve 的文章
文章代碼(AID): #1SBtzjO0 (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 7 之 10 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共10篇)
‣ 更多 silenteve 的文章
文章代碼(AID): #1SBtzjO0 (Grad-ProbAsk)