作者magic83v (R7)
看板Grad-ProbAsk
標題[理工] 演算法 第六章習題
時間Fri Dec 28 15:12:07 2018
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1545981130.A.60B.html
1F：→ rockieloser: 下限很難證吧 12/28 15:18
2F：推 w199381: 時間複雜度可以是任何asymptotic notation 只是上限是比 12/28 15:27
3F：→ w199381: 較容易證明的 12/28 15:27
4F：推 w199381: 且容易比較 12/28 15:30
5F：推 w199381: 再去確認定義後好像也不對QQ 別理我 12/28 15:34
6F：→ sdfg014025xx: 1. 沒有特別說過NPC的問題worst case 是在指數吧 2 12/28 18:22
7F：→ sdfg014025xx: 我的理解是通常估算時間複雜度都是想知道上限 12/28 18:22
8F：推 JKLee: 如果證出任一題NPC一定不能在polynomial time內解出 12/28 20:15
9F：→ JKLee: 那就代表P不等於NP 12/28 20:15
10F：→ JKLee: 但是目前無人能證出到底P=NP還是P!=NP 12/28 20:16
11F：→ JKLee: 所以第一題是false 12/28 20:22