[理工] 106中央资工算法 AAQ8 PTT批踢踢实业坊

[理工] 106中央资工算法

楼主: AAQ8 (不要就是要) 2019-01-21 17:57:20

https://i.imgur.com/HVeWcku.jpg
有爬过版上105中央资工的文章
题目有点不一样
不知道我这写对不对
(a)problem X存在polynomial-time reduction将problem X reduce到problem Y，则prob
lem Y为NP-hard。
(b)若problem Y存在一个算法在polynomial-time时间内解出，则problem Y为NP。
麻烦各位一下
谢谢

作者: z3588191 2019-01-21 18:10:00

A应该要多写X为NPB应该是说Y的解可以在poly-time内verify你B写的是P的定义

作者: krusnoopy (push) 2019-01-21 19:09:00

(a)为啥X还要说是NP 不是都说X是NPC了

作者: skyHuan (Huan) 2019-01-21 19:09:00

a题目已经说X是NPC了，原本写那样应该不用改吧(?b改完之后应该是对的~

作者: z3588191 2019-01-21 20:13:00

说明NPC为NP比较完整一些吧

作者: skyHuan (Huan) 2019-01-21 21:32:00

NPC一定是NP啊...

作者: krusnoopy (push) 2019-01-21 21:38:00

不是阿你还不如讲说因为X是NP-hard 你只拿一个NP问题来做reduction 证明又不成立要证明NP-hard 不一定要拿NPC来做reduction 但是一定要拿NP-hard问题来做

作者: skyHuan (Huan) 2019-01-21 22:33:00

https://i.imgur.com/mefKjlC.jpg所以要证一个问题是NP-hard法1. 根据定义证"所有"NP都reduce到他法2. 找"一个"NPC问题reduce到他

作者: krusnoopy (push) 2019-01-21 22:38:00

找一个NP-hard reduce也可以

作者: skyHuan (Huan) 2019-01-21 22:44:00

对XD 可是课本只有教NPC的reduce就快崩溃了QQ其实用NPC reduce也是NP hard的概念(?) 他也是NP hard

作者: krusnoopy (push) 2019-01-21 22:46:00

对所以我才说与其讲NP 还不如讲是NP-hard有些NP-hard问题不是NPC 所以我觉得讲清楚点比较好～这题我还是觉得知道X是NPC就够了不用特别写

继续阅读

[理工] 107 清大计系JohnnyJ [理工] 101台大计系kaidi620 [理工] 101中央线代aleswell [理工] 一起写台大计系b10007034 [理工] 计组题库AAQ8 离散关系ncdonalds123 [理工] 台大100记系kaidi620 104 中山资结supergotenks [理工] 106台大电机丙计系对答案moozkito [理工] 106成大离散o5739201