Re: [理工] 103 交大資演 NP問題

[joeboy (揪立)]

http://i.imgur.com/kbciU1u.jpg
同樣是第二個問題
有關下面編輯的話我複製一遍
"因為 longest path problem 可以 reduce 到這個問題的 decision 版本:

在限制 instance graph 含有正 cycle 的情形下,
longest path problem 仍為 NP-complete

所以將 LP 問題之 problem instance G 中所有邊的 weight 皆取負

則可成為此問題的一個 problem instance G'

這樣找到 G' 的 shortest simple path 就相當於找到 G 的 longest simple path"

這個已經是在是在證明NP-HARD了吧？

網路上也有查到，可以用longest path reduce過去，如果是simple path的話

不知道有沒有其他人有更好的解釋呢？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.11.240
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484466532.A.DC3.html
※ 編輯: joeboy (42.73.11.240), 01/15/2017 15:49:45
※ 編輯: joeboy (42.73.11.240), 01/15/2017 15:50:37
→ joeboy: QQ有人知道這個嗎
→ HEroKuma: 原問題是NP,又能歸約成NP-hard的LP問題,所以原問題是NPC
→ joeboy: 主要是因為板上對出來的答案給3，補習班老師也說3，不太
→ joeboy: 知道為什麼QQ
→ HEroKuma: 既不是P又不是NP-hard, 那就是NP 我怎麼看原推文說答案
→ HEroKuma: 是NPC?
→ joeboy: 我上面複製的這句話是補習班老師說的，他說是NP問題QQ
→ joeboy: http://i.imgur.com/2nu1h60.jpg
→ HEroKuma: longest path problem可以reduce成這個問題的decision版
→ HEroKuma: 代表他被reduce成一個NP問題
→ HEroKuma: 而把所有邊都取負的並找之LP, 假設找到一條P是最大
→ HEroKuma: 把邊的正負號改回來結果仍為LP
→ HEroKuma: 抱歉我邊打邊想 可能會回有點慢= =
→ HEroKuma: 不對 改回來不會是LP 那句無視
推 FRAXIS: 這問題是 NPC
→ joeboy: 嗯嗯，看來答案給錯了QQ
→ HEroKuma: 怎麼想都跟我一開始打的一樣, 不懂為什麼是NP....
→ HEroKuma: 然後一寫完就看到F大的回應 我就釋懷了XDD
→ joeboy: 他那個已經是明確證明NP-Hard了QQ如果是證明NP的話應該要
→ joeboy: 有一個輸入X跟一個certificate Y，然後找一個容易驗證的
→ joeboy: 演算法A使得A(X,Y)=1