作者AAQ8 ()
看板Grad-ProbAsk
標題[理工] 106中央資工演算法
時間Mon Jan 21 17:57:20 2019
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1548064643.A.E8A.html
1F：→ z3588191: A應該要多寫X為NP01/21 18:10
2F：→ z3588191: B應該是說Y的解可以在poly-time內verify01/21 18:13
3F：→ z3588191: 你B寫的是P的定義01/21 18:13
(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
4F：→ krusnoopy: (a)為啥X還要說是NP 不是都說X是NPC了 01/21 19:09
5F：推 skyHuan: a題目已經說X是NPC了，原本寫那樣應該不用改吧(? 01/21 19:09
6F：→ skyHuan: b改完之後應該是對的~ 01/21 19:10
7F：推 z3588191: 說明NPC為NP比較完整一些吧 01/21 20:13
8F：推 skyHuan: NPC一定是NP啊... 01/21 21:32
9F：推 krusnoopy: 不是阿 你還不如講說因為X是NP-hard 你只拿一個NP問題 01/21 21:38
10F：→ krusnoopy: 來做reduction 證明又不成立 01/21 21:38
11F：推 krusnoopy: 要證明NP-hard 不一定要拿NPC來做reduction 但是一定 01/21 21:45
12F：→ krusnoopy: 要拿NP-hard問題來做 01/21 21:45
14F：→ skyHuan: 所以要證一個問題是NP-hard 01/21 22:33
15F：→ skyHuan: 法1. 根據定義證"所有"NP都reduce到他 01/21 22:33
16F：→ skyHuan: 法2. 找"一個"NPC問題reduce到他 01/21 22:33
17F：→ krusnoopy: 找一個NP-hard reduce也可以 01/21 22:38
18F：推 skyHuan: 對XD 可是課本只有教NPC的reduce就快崩潰了QQ 01/21 22:44
19F：→ skyHuan: 其實用NPC reduce也是NP hard的概念(?) 他也是NP hard 01/21 22:44
20F：→ krusnoopy: 對 所以我才說 與其講NP 還不如講是NP-hard 01/21 22:46
21F：→ krusnoopy: 有些NP-hard問題不是NPC 所以我覺得講清楚點比較好～ 01/21 22:47
22F：→ krusnoopy: 這題我還是覺得知道X是NPC就夠了 不用特別寫 01/21 22:48