作者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/cn.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