作者eggy1018 (羅密歐與豬過夜)
看板Grad-ProbAsk
標題[理工] Time complexity, NP
時間Thu Dec 27 11:19:50 2018
想請問版上各位幾題，
https://i.imgur.com/fMTSPKA.jpg
以上幾題是F,F,T
想請教這一題的概念是什麼，這一題的概念是很單純的比較嗎...？
還是說可以用reduce 的概念去想呢？以此概念來想的話就是，B reduces 到A所以A比B難
。
因為跟林立宇的答案不太一樣QQ
麻煩各位大大幫忙了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.73.184
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1545880793.A.D35.html
1F：推 wei12f8158: 第一題如果帶A=O(n^2)就不成立，所以False，第二題帶A 12/27 13:49
2F：→ wei12f8158: =O(1)就不成立，所以False，第三題因爲nlogn<n^2，所 12/27 13:49
3F：→ wei12f8158: 以如果要B>n^2的話代表A一定要>n^2，所以True 12/27 13:49
4F：→ eggy1018: 第一題如果用reduce 的想法去想，B如果本身O(n) 可以解 12/27 15:15
5F：→ eggy1018: ，只是為了用A解所以reduce到A花了O(nlogn) 那麼怎麼能 12/27 15:15
6F：→ eggy1018: 肯定B就是O(lower bound of A)? 12/27 15:15
7F：→ eggy1018: 同樣的，A也可能可以reduce到B，但...題目給的是B reduc 12/27 15:17
8F：→ eggy1018: es 到A, 所以我假設A比B難，不知道這樣能不能QQ 謝謝W大 12/27 15:17
9F：→ eggy1018: 的回答 12/27 15:17
10F：推 nannnnn: 我在想老師會不會是用若p則q的等價命題非q則非p看這題 12/27 23:42
11F：→ nannnnn: 如果用reduce的看法寫這題我會寫F F F吧 12/27 23:43