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

看板Grad-ProbAsk作者時間5年前 (2019/01/21 17:57), 5年前編輯推噓7(7推 0噓 15→)
留言22則, 3人參與, 5年前最新討論串1/2 (看更多)
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
→
01/21 18:10, 5年前 , 1F
A應該要多寫X為NP
01/21 18:10, 1F
→
01/21 18:13, 5年前 , 2F
B應該是說Y的解可以在poly-time內verify
01/21 18:13, 2F
→
01/21 18:13, 5年前 , 3F
你B寫的是P的定義
01/21 18:13, 3F
(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
→
01/21 19:09, 5年前 , 4F
(a)為啥X還要說是NP 不是都說X是NPC了
01/21 19:09, 4F
推
01/21 19:09, 5年前 , 5F
a題目已經說X是NPC了，原本寫那樣應該不用改吧(?
01/21 19:09, 5F
→
01/21 19:10, 5年前 , 6F
b改完之後應該是對的~
01/21 19:10, 6F
推
01/21 20:13, 5年前 , 7F
說明NPC為NP比較完整一些吧
01/21 20:13, 7F
推
01/21 21:32, 5年前 , 8F
NPC一定是NP啊...
01/21 21:32, 8F
推
01/21 21:38, 5年前 , 9F
不是阿 你還不如講說因為X是NP-hard 你只拿一個NP問題
01/21 21:38, 9F
→
01/21 21:38, 5年前 , 10F
來做reduction 證明又不成立
01/21 21:38, 10F
推
01/21 21:45, 5年前 , 11F
要證明NP-hard 不一定要拿NPC來做reduction 但是一定
01/21 21:45, 11F
→
01/21 21:45, 5年前 , 12F
要拿NP-hard問題來做
01/21 21:45, 12F
推
01/21 22:33, 5年前 , 13F
01/21 22:33, 13F
→
01/21 22:33, 5年前 , 14F
所以要證一個問題是NP-hard
01/21 22:33, 14F
→
01/21 22:33, 5年前 , 15F
法1. 根據定義證"所有"NP都reduce到他
01/21 22:33, 15F
→
01/21 22:33, 5年前 , 16F
法2. 找"一個"NPC問題reduce到他
01/21 22:33, 16F
→
01/21 22:38, 5年前 , 17F
找一個NP-hard reduce也可以
01/21 22:38, 17F
推
01/21 22:44, 5年前 , 18F
對XD 可是課本只有教NPC的reduce就快崩潰了QQ
01/21 22:44, 18F
→
01/21 22:44, 5年前 , 19F
其實用NPC reduce也是NP hard的概念(?) 他也是NP hard
01/21 22:44, 19F
→
01/21 22:46, 5年前 , 20F
對 所以我才說 與其講NP 還不如講是NP-hard
01/21 22:46, 20F
→
01/21 22:47, 5年前 , 21F
有些NP-hard問題不是NPC 所以我覺得講清楚點比較好～
01/21 22:47, 21F
→
01/21 22:48, 5年前 , 22F
這題我還是覺得知道X是NPC就夠了 不用特別寫
01/21 22:48, 22F
‣ 更多 AAQ8 的文章
文章代碼(AID): #1SHPU3wA (Grad-ProbAsk)
‣ 更多 AAQ8 的文章
文章代碼(AID): #1SHPU3wA (Grad-ProbAsk)