[問題] NP的觀念
看板Prob_Solve (計算數學 Problem Solving)作者mqazz1 (無法顯示)時間13年前 (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
→
07/29 20:32, , 1F
07/29 20:32, 1F
→
07/29 20:34, , 2F
07/29 20:34, 2F
→
07/29 20:40, , 3F
07/29 20:40, 3F
推
07/30 16:29, , 4F
07/30 16:29, 4F
推
08/11 03:01, , 5F
08/11 03:01, 5F
推
08/27 15:47, , 6F
08/27 15:47, 6F
→
08/27 15:48, , 7F
08/27 15:48, 7F
→
08/27 15:49, , 8F
08/27 15:49, 8F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
