[問題] NP的觀念

看板Prob_Solve作者mqazz1 (無法顯示)時間14年前 (2011/07/29 20:12)推噓3(3推 0噓 5→)

留言8則, 5人參與討論串1/1

let A and B be two computational problems. If we can find a linear time algorithm to transform A to B, i.e., the inputs to A is transform to the inputs to B and the solution to B is transform A, both can be done in O(n) time. (1) we can say that A is at least as hard as B (2) we can solve B by solving A (3) if the least possible computing time required(or the lower bound) for solving A is Ω(nlogn), B also has Ω(nlogn) lower bound 請問上面這三點哪些是對的? A reduce to B 這樣是B比較難這題這樣寫是哪個比較難? 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.228.27.178

→

Favonia

07/29 20:32, , 1^F

07/29 20:32, 1^F

→

Favonia

07/29 20:34, , 2^F

07/29 20:34, 2^F

→

mqazz1

07/29 20:40, , 3^F

07/29 20:40, 3^F