作者ponponjerry (just do it)
看板Grad-ProbAsk
标题[理工] NP问题
时间Fri Jan 25 01:53:17 2019
https://i.imgur.com/4QNa9jp.jpg
想请问这题的(e)，
若是把NP-cpmplete改成NP-hard，
这个选项会变成true吗？
https://i.imgur.com/D7tmJLt.jpg
请问这题的(3)为什麽是false
我是想说O(nlogn+Ω(n^2))=θ(Ω(n^2))
是不是不能这样看XD
谢谢大家帮忙，祝各位考试顺利
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 219.70.183.56
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1548352400.A.C35.html
1F：推 skyHuan: (e) 写反了吧，3SAT reduce到问题L => L是NP hard01/25 01:57
3F：推 skyHuan: (3)我是这样想，应该可以看成B可以在nlogn的时间reduce01/25 02:06
4F：→ skyHuan: 到A，A的复杂度又比nlogn大，表示B不难於A，所以B的lower01/25 02:06
5F：→ skyHuan: bound可能比A还低01/25 02:06
6F：→ skyHuan: (3)的想法不确定有错还请指正QQ01/25 02:07
谢谢sky哥，好像略懂了，我发现我(3)那个根本耍脑乱打应该要打成O(nlogn+T(n))=O(T(n))，这样就跟你说得对起来了
※ 编辑: ponponjerry (219.70.183.56), 01/25/2019 02:35:57
8F：推 skyHuan: 喔喔喔喔喔楼上这篇好清楚>///< 01/25 10:23
9F：推 skyHuan: 借板问一下，楼上那篇的(2)看了还是没有很懂>< 01/25 12:22
13F：→ rockieloser: 感觉跟他内文最後一段很像 01/25 13:09
14F：推 ekids1234: 用JK大的观念推sky大的後面那段的话感觉是对的 01/25 13:28
15F：→ ekids1234: 但前面 reduce 那段我不太清楚能不能这样想 01/25 13:33
16F：推 ekids1234: 另外我想问一个很基础的:一个 n(polynomial)就能解决的 01/25 13:37
17F：→ ekids1234: 可以算是 O(n^2) 吗 ? 01/25 13:38
19F：→ JKLee: 11(3)的题目可翻译成: 01/27 15:11
20F：→ JKLee: Suppose that 01/27 15:11
21F：→ JKLee: "if T_A ≦ T(n), 01/27 15:11
22F：→ JKLee: then T_B ≦ n*lg(n) + T(n)". 01/27 15:11
23F：→ JKLee: If T_A ≧ n^2, then T_B ≧ n^2. 01/27 15:11