[理工] 演算法NP Complete

[wilson50101 (我覺得我還不錯啊)]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1539831323.A.0F0.html
推 butterflyred: longest path problem is np-complete 在tree上O(v)
→ butterflyred: 可解
→ wilson50101: 哦 所以如果換條件像是DAG求longest path這種特殊條
→ wilson50101: 件下也要算進去哦
推 alan23273850: input 這個詞改成 instance 比較好
→ wilson50101: 好的 感謝
推 FRAXIS: 這題是說 NPC 還沒有人證明出至少要 exponential time 才
→ FRAXIS: 可解  因為這就表示 P != NP
→ wilson50101: 回樓上:
→ wilson50101: 所以意思是目前P=NP與否尚未定論是因為沒有人證出這
→ wilson50101: 個選項所以沒辦法確定P!=NP
→ wilson50101: 是這樣嗎？
推 FRAXIS: 是的
→ wilson50101: ok thx