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