[理工] 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