作者matt530 (懂吗)
看板Grad-ProbAsk
标题[理工] 106清大 计算机科学 两问 5 8
时间Tue Jan 29 22:15:41 2019
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1548771343.A.CF9.html
1F：→ yp195126: 5.D 直接代公式01/29 23:29
2F：→ RinHizakura: 5的de 展开最高项就是n^b 所以d对e错？01/29 23:47
3F：→ RinHizakura: 证明是np-hard 的话 只要可以reduce到任一个已知的N01/29 23:48
4F：→ RinHizakura: pc 就是了01/29 23:48
啊对 ！！了解了谢谢
※ 编辑: matt530 (223.139.87.176), 01/30/2019 00:43:08