作者wilson50101 (我覺得我還不錯啊)
看板Grad-ProbAsk
標題[理工] 演算法NP Complete
時間Thu Oct 18 10:55:21 2018
http://i.imgur.com/XYyWZ2O.jpg
不好意思想問一下第一題的c
解答說並不一定要花指數時間才能解任意NPC之input。看不太懂他的意思是什麼
是指說有可能花比指數等級時間還多(O(n!)之類)的嗎？
-----
Sent from JPTT on my Asus ASUS_Z016D.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.10.199.169
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1539831323.A.0F0.html
1F：推 butterflyred: longest path problem is np-complete 在tree上O(v) 10/18 12:31
2F：→ butterflyred: 可解 10/18 12:31
3F：→ wilson50101: 哦 所以如果換條件像是DAG求longest path這種特殊條 10/18 12:34
4F：→ wilson50101: 件下也要算進去哦 10/18 12:34
5F：推 alan23273850: input 這個詞改成 instance 比較好 10/18 16:49
6F：→ wilson50101: 好的 感謝 10/18 17:03
7F：推 FRAXIS: 這題是說 NPC 還沒有人證明出至少要 exponential time 才 10/18 20:33
8F：→ FRAXIS: 可解 因為這就表示 P != NP 10/18 20:33
9F：→ wilson50101: 回樓上: 10/18 22:54
10F：→ wilson50101: 所以意思是目前P=NP與否尚未定論是因為沒有人證出這 10/18 22:54
11F：→ wilson50101: 個選項所以沒辦法確定P!=NP 10/18 22:54
12F：→ wilson50101: 是這樣嗎？ 10/18 22:54
13F：推 FRAXIS: 是的 10/19 10:28
14F：→ wilson50101: ok thx 10/19 10:38