[理工] 算法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

继续阅读