[理工] 106清大計算機科學兩問 5 8 matt530 PTT批踢踢實業坊

[理工] 106清大計算機科學兩問 5 8

作者: matt530 (懂嗎) 2019-01-29 22:15:41

https://i.imgur.com/PN8sZ5z.jpg
第5題 DE 選項
好像有點印象又有點模糊
找筆記也沒有寫到不確定答案是什麼
https://i.imgur.com/u5JzD2J.jpg
再來第8是要如何證明是NP hard ?
證明NP hard 是先得證明比NPC難嗎？
定義是說不確定是不是能在polynomial time 驗證的問題，我的想法是想從補圖試試看不
過完全沒有下筆點

作者: yp195126 (我睡故我在) 2019-01-29 23:29:00

5.D 直接代公式

作者: RinHizakura (凜凜緋櫻) 2019-01-29 23:47:00

5的de 展開最高項就是n^b 所以d對e錯？證明是np-hard 的話只要可以reduce到任一個已知的Npc 就是了

繼續閱讀

[理工] 98交大OSkaidi620 [理工] 102中央數學a80242002 [理工] 資結 sort找最大,次大,最小ncdonalds123 [理工] 105 中央計系haniwang [控制] Lyapunov函數a0972969533 交大OS 95成大OSkaidi620 [理工] [作業系統］fork 問題lionccc [理工] 104中山計組AAQ8 [理工] 107中央計組rustw2010 [理工] 107台大電機丙資結對答案ko330

[理工] 106清大 計算機科學 兩問 5 8

[理工] 106清大計算機科學兩問 5 8