[理工] NP問題

看板Grad-ProbAsk作者 (just do it)時間5年前 (2019/01/25 01:53), 5年前編輯推噓7(7推 0噓 16→)
留言23則, 4人參與, 5年前最新討論串3/3 (看更多)
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
推
01/25 01:57, 5年前 , 1F
(e) 寫反了吧，3SAT reduce到問題L => L是NP hard
01/25 01:57, 1F
→
01/25 02:00, 5年前 , 2F
01/25 02:00, 2F
推
01/25 02:06, 5年前 , 3F
(3)我是這樣想，應該可以看成B可以在nlogn的時間reduce
01/25 02:06, 3F
→
01/25 02:06, 5年前 , 4F
到A，A的複雜度又比nlogn大，表示B不難於A，所以B的lower
01/25 02:06, 4F
→
01/25 02:06, 5年前 , 5F
bound可能比A還低
01/25 02:06, 5F
→
01/25 02:07, 5年前 , 6F
(3)的想法不確定有錯還請指正QQ
01/25 02:07, 6F
謝謝sky哥，好像略懂了，我發現我(3)那個根本耍腦亂打應該要打成O(nlogn+T(n))=O(T(n))，這樣就跟你說得對起來了 ※ 編輯: ponponjerry (219.70.183.56), 01/25/2019 02:35:57
→
01/25 03:01, 5年前 , 7F
01/25 03:01, 7F
推
01/25 10:23, 5年前 , 8F
喔喔喔喔喔樓上這篇好清楚>///<
01/25 10:23, 8F
推
01/25 12:22, 5年前 , 9F
借板問一下，樓上那篇的(2)看了還是沒有很懂><
01/25 12:22, 9F
→
01/25 12:22, 5年前 , 10F
01/25 12:22, 10F
→
01/25 12:22, 5年前 , 11F
01/25 12:22, 11F
→
01/25 12:22, 5年前 , 12F
01/25 12:22, 12F
→
01/25 13:09, 5年前 , 13F
感覺跟他內文最後一段很像
01/25 13:09, 13F
推
01/25 13:28, 5年前 , 14F
用JK大的觀念推sky大的後面那段的話感覺是對的
01/25 13:28, 14F
→
01/25 13:33, 5年前 , 15F
但前面 reduce 那段我不太清楚能不能這樣想
01/25 13:33, 15F
推
01/25 13:37, 5年前 , 16F
另外我想問一個很基礎的:一個 n(polynomial)就能解決的
01/25 13:37, 16F
→
01/25 13:38, 5年前 , 17F
可以算是 O(n^2) 嗎 ?
01/25 13:38, 17F
推
01/27 15:11, 5年前 , 18F
沿用 #1S9Ft6TN (Grad-ProbAsk) 的定義，
01/27 15:11, 18F
→
01/27 15:11, 5年前 , 19F
11(3)的題目可翻譯成:
01/27 15:11, 19F
→
01/27 15:11, 5年前 , 20F
Suppose that
01/27 15:11, 20F
→
01/27 15:11, 5年前 , 21F
"if T_A ≦ T(n),
01/27 15:11, 21F
→
01/27 15:11, 5年前 , 22F
then T_B ≦ n*lg(n) + T(n)".
01/27 15:11, 22F
→
01/27 15:11, 5年前 , 23F
If T_A ≧ n^2, then T_B ≧ n^2.
01/27 15:11, 23F
‣ 更多 ponponjerry 的文章
文章代碼(AID): #1SIVkGmr (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 3 之 3 篇)：
排序： 最舊先 | 最新先 | 留言數
理工
8
26
[理工] NP問題 NP問題
ssssIssss
7年前, 02/07
理工
1
3
[理工] NP問題 NP問題
sooge
5年前, 01/20
理工
7
23
[理工] NP問題 NP問題
ponponjerry
5年前, 01/25
在新視窗開啟完整討論串 (共3篇)
‣ 更多 ponponjerry 的文章
文章代碼(AID): #1SIVkGmr (Grad-ProbAsk)