[理工] NP問題

[ponponjerry (just do it)]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1548352400.A.C35.html
推 skyHuan: (e) 寫反了吧，3SAT reduce到問題L => L是NP hard
→ skyHuan: #1SHPU3wA (Grad-ProbAsk)
推 skyHuan: (3)我是這樣想，應該可以看成B可以在nlogn的時間reduce
→ skyHuan: 到A，A的複雜度又比nlogn大，表示B不難於A，所以B的lower
→ skyHuan:  bound可能比A還低
→ skyHuan: (3)的想法不確定有錯還請指正QQ
謝謝sky哥，好像略懂了，我發現我(3)那個根本耍腦亂打應該要打成O(nlogn+T(n))=O(T(n))，這樣就跟你說得對起來了
※ 編輯: ponponjerry (219.70.183.56), 01/25/2019 02:35:57
→ rockieloser: #1S9Ft6TN (Grad-ProbAsk)
推 skyHuan: 喔喔喔喔喔樓上這篇好清楚>///<
推 skyHuan: 借板問一下，樓上那篇的(2)看了還是沒有很懂><
→ skyHuan: https://i.imgur.com/OheXo76.jpg
→ skyHuan: https://i.imgur.com/ulMXcpI.jpg
→ skyHuan: https://i.imgur.com/XADmbVS.jpg
→ rockieloser: 感覺跟他內文最後一段很像
推 ekids1234: 用JK大的觀念推sky大的後面那段的話感覺是對的
→ ekids1234: 但前面 reduce 那段我不太清楚能不能這樣想
推 ekids1234: 另外我想問一個很基礎的:一個 n(polynomial)就能解決的
→ ekids1234: 可以算是 O(n^2) 嗎 ?
推 JKLee: 沿用 #1S9Ft6TN (Grad-ProbAsk) 的定義，
→ JKLee: 11(3)的題目可翻譯成:
→ JKLee: Suppose that
→ JKLee: "if T_A ≦ T(n),
→ JKLee: then T_B ≦ n*lg(n) + T(n)".
→ JKLee: If T_A ≧ n^2, then T_B ≧ n^2.