→ yp195126: 5.D 直接代公式01/29 23:29
→ RinHizakura: 5的de 展開最高項就是n^b 所以d對e錯？01/29 23:47
→ RinHizakura: 證明是np-hard 的話 只要可以reduce到任一個已知的N01/29 23:48
→ RinHizakura: pc 就是了01/29 23:48
啊對 ！！瞭解了謝謝
※ 編輯: matt530 (223.139.87.176), 01/30/2019 00:43:08
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