※ 引述《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/cn.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