作者silenteve (沉默的EVE)
看板Grad-ProbAsk
標題[理工] 105交大資演
時間Fri Jan 4 23:44:42 2019
https://i.imgur.com/cMhXsG8.jpg
想問一下這題各個選項t or f 跟原因
答案好像是d
謝謝～
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.82.8.135
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1546616685.A.600.html
1F：→ sdfg014025xx: (A)NPC 是NPH和NP的交集 01/05 00:45
2F：推 eggy1018: (B)要先有一組certificates,並在polynomial time verify 01/05 01:23
3F：→ eggy1018: 才是NP 01/05 01:23
4F：推 eggy1018: (C)不太確定 我覺得是NP-complete 可以互相reduce 的條 01/05 01:25
5F：→ eggy1018: 件 01/05 01:25
6F：推 eggy1018: (E)反過來了，因為可以reduce到SAT表示SAT比較原問題難 01/05 01:27
7F：→ eggy1018: 解，此時仍沒辦法知道原問題多難，所以不能確定原問題NP 01/05 01:27
8F：→ eggy1018: -complete, 反過來才有辦法說明～ 01/05 01:27
9F：→ eggy1018: 以上有錯 還麻煩各位大大指正了 01/05 01:27
10F：推 FRAXIS: (C) NPH 可能比 NPC 難 所以不一定可以 reduce 01/05 03:09