[理工] 演算法 第六章習題

看板Grad-ProbAsk作者 (R7)時間7年前 (2018/12/28 15:12), 編輯推噓4(4推 0噓 7→)
留言11則, 4人參與, 7年前最新討論串1/1
https://i.imgur.com/64j8gs5.jpg
https://i.imgur.com/dmWKFay.jpg
想確認一下 第一題F是因為 最差還有階乘時間嗎 註1:npc在sub exponential 解決是定理 註3:3-sat不可在sub exponential 解決 這邊是什麼意思 第二題True 時間複雜度就是指upper bound？ 感謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.247.97.3 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1545981130.A.60B.html
→
12/28 15:18, 7年前 , 1F
下限很難證吧
12/28 15:18, 1F
推
12/28 15:27, 7年前 , 2F
時間複雜度可以是任何asymptotic notation 只是上限是比
12/28 15:27, 2F
→
12/28 15:27, 7年前 , 3F
較容易證明的
12/28 15:27, 3F
推
12/28 15:30, 7年前 , 4F
且容易比較
12/28 15:30, 4F
推
12/28 15:34, 7年前 , 5F
再去確認定義後好像也不對QQ 別理我
12/28 15:34, 5F
→
12/28 18:22, 7年前 , 6F
1. 沒有特別說過NPC的問題worst case 是在指數吧 2
12/28 18:22, 6F
→
12/28 18:22, 7年前 , 7F
我的理解是通常估算時間複雜度都是想知道上限
12/28 18:22, 7F
推
12/28 20:15, 7年前 , 8F
如果證出任一題NPC一定不能在polynomial time內解出
12/28 20:15, 8F
→
12/28 20:15, 7年前 , 9F
那就代表P不等於NP
12/28 20:15, 9F
→
12/28 20:16, 7年前 , 10F
但是目前無人能證出到底P=NP還是P!=NP
12/28 20:16, 10F
→
12/28 20:22, 7年前 , 11F
所以第一題是false
12/28 20:22, 11F
‣ 更多 magic83v 的文章
文章代碼(AID): #1S9SpAOB (Grad-ProbAsk)