[理工] 105交大資演 silenteve PTT批踢踢實業坊

[理工] 105交大資演

作者: silenteve (沉默的EVE) 2019-01-04 23:44:42

https://i.imgur.com/cMhXsG8.jpg
想問一下這題各個選項t or f 跟原因
答案好像是d
謝謝～

作者: sdfg014025xx (隨便就好) 2019-01-05 00:45:00

(A)NPC 是NPH和NP的交集

作者: eggy1018 (ç¾…å¯†æèˆ‡è±¬éŽå¤œ) 2019-01-05 01:23:00

(B)要先有一組certificates,並在polynomial time verify才是NP(C)不太確定我覺得是NP-complete 可以互相reduce 的條件(E)反過來了，因為可以reduce到SAT表示SAT比較原問題難解，此時仍沒辦法知道原問題多難，所以不能確定原問題NP-complete, 反過來才有辦法說明～以上有錯還麻煩各位大大指正了

作者: FRAXIS (喔喔) 2019-01-05 03:09:00

繼續閱讀

[理工] 線代正交補空間st945712 [理工] 計組題庫AAQ8 [理工] 101 中央資工線代gaowei16 [理工] 多級放大器電子學pochen9 [理工] 中央多選題答題計分方式請益st945712 [理工] 106中山OSveryhungry12 [理工] 線代第八章AAQ8 106中央資演eric21489 [理工] 關於數位邏輯o5739201 [理工] 離散偏序集 10-6jojoboy0115