[理工] 演算法NP Complete wilson50101 PTT批踢踢實業坊

作者: wilson50101 (我覺得我還不錯啊) 2018-10-18 10:55:21

http://i.imgur.com/XYyWZ2O.jpg
不好意思想問一下第一題的c
解答說並不一定要花指數時間才能解任意NPC之input。看不太懂他的意思是什麼
是指說有可能花比指數等級時間還多(O(n!)之類)的嗎？

作者: butterflyred (butterflyred) 2018-10-18 12:31:00

longest path problem is np-complete 在tree上O(v)可解

作者: wilson50101 (我覺得我還不錯啊) 2018-10-18 12:34:00

哦所以如果換條件像是DAG求longest path這種特殊條件下也要算進去哦

作者: alan23273850 2018-10-18 16:49:00

input 這個詞改成 instance 比較好

作者: wilson50101 (我覺得我還不錯啊) 2018-10-18 17:03:00

好的感謝

作者: FRAXIS (喔喔) 2018-10-18 20:33:00

這題是說 NPC 還沒有人證明出至少要 exponential time 才可解因為這就表示 P != NP

作者: wilson50101 (我覺得我還不錯啊) 2018-10-18 22:54:00

回樓上:所以意思是目前P=NP與否尚未定論是因為沒有人證出這個選項所以沒辦法確定P!=NP是這樣嗎？

作者: FRAXIS (喔喔) 2018-10-19 10:28:00

是的

作者: wilson50101 (我覺得我還不錯啊) 2018-10-19 10:38:00

ok thx

繼續閱讀