Re: [理工] Time complexity, NP
: 以上幾題是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://www.ptt.cc/bbs/Grad-ProbAsk/M.1545928134.A.757.html
※ 編輯: JKLee (1.160.99.38), 12/28/2018 01:05:48
推
12/28 01:22,
5年前
, 1F
12/28 01:22, 1F
※ 編輯: JKLee (1.160.99.38), 12/28/2018 02:04:47
推
12/28 08:03,
5年前
, 2F
12/28 08:03, 2F
推
12/28 18:34,
5年前
, 3F
12/28 18:34, 3F
推
12/28 19:10,
5年前
, 4F
12/28 19:10, 4F
推
12/28 22:29,
5年前
, 5F
12/28 22:29, 5F
※ 編輯: JKLee (1.160.99.38), 12/29/2018 00:10:01
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：