※ 引述《eggy1018 (羅密歐與豬過夜)》之銘言： : 想請問版上各位幾題， : https://i.imgur.com/fMTSPKA.jpg : 以上幾題是F,F,T : 想請教這一題的概念是什麼，這一題的概念是很單純的比較嗎...？ : 還是說可以用reduce 的概念去想呢？以此概念來想的話就是，B reduces 到A所以A比B難 : 。 : 因為跟林立宇的答案不太一樣QQ : 麻煩各位大大幫忙了 定義符號: ≦, ≧ f(n) ≦ g(n) 代表 f(n) = O(g(n)) f(n) ≧ g(n) 代表 f(n) = Ω(g(n)) 令 解 A 所需的時間為 T_A 解 B 所需的時間為 T_B 將下面這句話 "if we could solve A in the time O(T(n)), then we could solve B in time O(n*lg(n) + T(n))" 轉成符號 "if T_A ≦ T(n), then T_B ≦ n*lg(n) + T(n)." -------------(i) 為什麼可以推出(i)? 題目沒有說的是: 因為 T_B ≦ n*lg(n) + T_A , -------------------------------(ii) 所以才能推出(i) 如果你沒有看出(ii)的話，後面就不會做了。 第(1)題說，如果 T_A ≧ n*lg(n) ，則 T_B ≧ n*lg(n) 。 你無法從(ii)推出這個結果，所以(1)錯。 第(2)題說，如果 T_B ≧ n*lg(n) ，則 T_A ≧ n*lg(n) 。 你無法從(ii)推出這個結果，所以(2)錯。 第(3)題說，如果 T_B ≧ n^2 ，則 T_A ≧ n^2 。 n^2 ≦ T_B ≦ n*lg(n) + T_A (by (ii)) => n^2 ≦ T_A 所以(3)對。 ---------- 補充: 1. 令 T_A, T_B 分別為解 A, B 所需時間的最緊 upper bound 若 Problem B 需花 T_R 的時間 reduce 到 Problem A 則 T_B ≦ T_R + T_A ------------------------------------(iii) 2. B 可以 polynomial time 內 reduce 到 A ，不代表 A 比 B 難 也就是說不代表 T_B ≦ T_A --------------------------------(iv) 3. 用符號再說明一次: 當 T_R (reduce時間) T_A (解A所需時間) T_B (解B所需時間) 都是 polynomial time 時 你無法從(iii)推出(iv) 4. 創造NP與reduce...等這些東西是為了解決難題(無法在 polynomial time 解決的問題)， 所以 T_A, T_B 通常不會都是 polynomial time。 T_R 為 polynomial (已經規定的reduce time限制) 且 T_A 或 T_B 其中之一超過 polynomial time 你就可以從(iii)(B reduce 到 A) 推到(iv)(A 比 B 難) 5. 嚴格來說，應該要講 B 不難於 A， 但為了方便理解，我這裡還是寫 A 比 B 難。 6. 難度的定義有兩種， 第一種是直接比時間複雜度，花越多時間的越難。 我上面講的難度都是指第一種。 第二種是兩問題之間要有reduce關係才能比較難度。 第二種定義主要是針對非polynomial time的問題。 要是兩個問題都是polynomial time可以解的， 就會發生難的問題可以reduce到簡單的問題這種奇怪的狀況。 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.99.38 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1545928134.A.757.html ※ 編輯: JKLee (1.160.99.38), 12/28/2018 01:05:48 ※ 編輯: JKLee (1.160.99.38), 12/28/2018 02:04:47 ※ 編輯: JKLee (1.160.99.38), 12/29/2018 00:10:01