[理工] 演算法NP Complete

看板Grad-ProbAsk作者 (我覺得我還不錯啊)時間7年前 (2018/10/18 10:55), 編輯推噓4(4推 0噓 10→)
留言14則, 4人參與, 7年前最新討論串1/1
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
推
10/18 12:31, 7年前 , 1F
longest path problem is np-complete 在tree上O(v)
10/18 12:31, 1F
→
10/18 12:31, 7年前 , 2F
可解
10/18 12:31, 2F
→
10/18 12:34, 7年前 , 3F
哦 所以如果換條件像是DAG求longest path這種特殊條
10/18 12:34, 3F
→
10/18 12:34, 7年前 , 4F
件下也要算進去哦
10/18 12:34, 4F
推
10/18 16:49, 7年前 , 5F
input 這個詞改成 instance 比較好
10/18 16:49, 5F
→
10/18 17:03, 7年前 , 6F
好的 感謝
10/18 17:03, 6F
推
10/18 20:33, 7年前 , 7F
這題是說 NPC 還沒有人證明出至少要 exponential time 才
10/18 20:33, 7F
→
10/18 20:33, 7年前 , 8F
可解 因為這就表示 P != NP
10/18 20:33, 8F
→
10/18 22:54, 7年前 , 9F
回樓上:
10/18 22:54, 9F
→
10/18 22:54, 7年前 , 10F
所以意思是目前P=NP與否尚未定論是因為沒有人證出這
10/18 22:54, 10F
→
10/18 22:54, 7年前 , 11F
個選項所以沒辦法確定P!=NP
10/18 22:54, 11F
→
10/18 22:54, 7年前 , 12F
是這樣嗎？
10/18 22:54, 12F
推
10/19 10:28, 7年前 , 13F
是的
10/19 10:28, 13F
→
10/19 10:38, 7年前 , 14F
ok thx
10/19 10:38, 14F
‣ 更多 wilson50101 的文章
文章代碼(AID): #1Rn_OR3m (Grad-ProbAsk)