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

看板Grad-ProbAsk作者 (懂嗎)時間6年前 (2019/01/29 22:15), 6年前編輯推噓0(0推 0噓 4→)
留言4則, 2人參與, 6年前最新討論串1/1
https://i.imgur.com/PN8sZ5z.jpg
第5題 DE 選項 好像有點印象又有點模糊 找筆記也沒有寫到 不確定答案是什麼 https://i.imgur.com/u5JzD2J.jpg
再來第8是要如何證明是NP hard ? 證明NP hard 是先得證明比NPC難嗎 ？ 定義是說不確定是不是能在polynomial time 驗證的問題，我的想法是想從補圖試試看不 過完全沒有下筆點 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.139.87.176 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1548771343.A.CF9.html
→
01/29 23:29, 6年前 , 1F
5.D 直接代公式
01/29 23:29, 1F
→
01/29 23:47, 6年前 , 2F
5的de 展開最高項就是n^b 所以d對e錯？
01/29 23:47, 2F
→
01/29 23:48, 6年前 , 3F
證明是np-hard 的話 只要可以reduce到任一個已知的N
01/29 23:48, 3F
→
01/29 23:48, 6年前 , 4F
pc 就是了
01/29 23:48, 4F
啊對 ！！瞭解了謝謝 ※ 編輯: matt530 (223.139.87.176), 01/30/2019 00:43:08
‣ 更多 matt530 的文章
文章代碼(AID): #1SK60Fpv (Grad-ProbAsk)