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
谢谢大家帮忙，祝各位考试顺利

(e) 写反了吧，3SAT reduce到问题L => L是NP hard#1SHPU3wA (Grad-ProbAsk)(3)我是这样想，应该可以看成B可以在nlogn的时间reduce到A，A的复杂度又比nlogn大，表示B不难于A，所以B的lowerbound可能比A还低(3)的想法不确定有错还请指正QQ

喔喔喔喔喔楼上这篇好清楚>///<借板问一下，楼上那篇的(2)看了还是没有很懂><https://i.imgur.com/OheXo76.jpghttps://i.imgur.com/ulMXcpI.jpghttps://i.imgur.com/XADmbVS.jpg

感觉跟他内文最后一段很像

用JK大的观念推sky大的后面那段的话感觉是对的但前面 reduce 那段我不太清楚能不能这样想另外我想问一个很基础的:一个 n(polynomial)就能解决的可以算是 O(n^2) 吗 ?

沿用 #1S9Ft6TN (Grad-ProbAsk) 的定义，11(3)的题目可翻译成:Suppose that"if T_A ≦ T(n),then T_B ≦ n*lg(n) + T(n)".If T_A ≧ n^2, then T_B ≧ n^2.