作者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/cn.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