[理工] 106中央資工演算法

[AAQ8 ()]

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。


麻煩各位一下

謝謝




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.9.163.6
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1548064643.A.E8A.html
→ z3588191: A應該要多寫X為NP
→ z3588191: B應該是說Y的解可以在poly-time內verify
→ z3588191: 你B寫的是P的定義
(a)若problem X可被non-deterministic algo在多項式時間內解決，且存在polynomial-t
ime reduction將problem X reduce到problem Y，則problem Y為NP-hard。

(b)若problem Y存在一個non-deterministic algo在polynomial-time時間內解出，則pro
blem Y為NP。

是修改成這樣嗎



※ 編輯: AAQ8 (39.9.163.6), 01/21/2019 18:30:34
→ krusnoopy: (a)為啥X還要說是NP 不是都說X是NPC了
推 skyHuan: a題目已經說X是NPC了，原本寫那樣應該不用改吧(?
→ skyHuan: b改完之後應該是對的~
推 z3588191: 說明NPC為NP比較完整一些吧
推 skyHuan: NPC一定是NP啊...
推 krusnoopy: 不是阿 你還不如講說因為X是NP-hard 你只拿一個NP問題
→ krusnoopy: 來做reduction 證明又不成立
推 krusnoopy: 要證明NP-hard 不一定要拿NPC來做reduction 但是一定
→ krusnoopy: 要拿NP-hard問題來做
推 skyHuan: https://i.imgur.com/mefKjlC.jpg
→ skyHuan: 所以要證一個問題是NP-hard
→ skyHuan: 法1. 根據定義證"所有"NP都reduce到他
→ skyHuan: 法2. 找"一個"NPC問題reduce到他
→ krusnoopy: 找一個NP-hard reduce也可以
推 skyHuan: 對XD 可是課本只有教NPC的reduce就快崩潰了QQ
→ skyHuan: 其實用NPC reduce也是NP hard的概念(?) 他也是NP hard
→ krusnoopy: 對 所以我才說 與其講NP 還不如講是NP-hard
→ krusnoopy: 有些NP-hard問題不是NPC 所以我覺得講清楚點比較好～
→ krusnoopy: 這題我還是覺得知道X是NPC就夠了 不用特別寫