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