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

[magic83v (R7)]

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
→ rockieloser: 下限很難證吧
推 w199381: 時間複雜度可以是任何asymptotic notation 只是上限是比
→ w199381: 較容易證明的
推 w199381: 且容易比較
推 w199381: 再去確認定義後好像也不對QQ 別理我
→ sdfg014025xx: 1. 沒有特別說過NPC的問題worst case 是在指數吧  2
→ sdfg014025xx: 我的理解是通常估算時間複雜度都是想知道上限
推 JKLee: 如果證出任一題NPC一定不能在polynomial time內解出
→ JKLee: 那就代表P不等於NP
→ JKLee: 但是目前無人能證出到底P=NP還是P!=NP
→ JKLee: 所以第一題是false