[問題] NP的觀念

[mqazz1 (無法顯示)]

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:hard的精確定義仰賴reduce的精確定義。然後你是用TM嗎？
→ Favonia:我的意思是說，允許的reduction恰好是所有O(n)時間演算法?
→ mqazz1:這個是研究所的考題 我想可能是比較通俗的定義吧@@?
推 shiuantzuo:都不對...
推 jfurseteidce:(1)A轉成B問題 所以B比A難 (2)藉由解B可以解A
推 Arim:第1點應該是要說B至少跟A一樣難 第二點是由A解B
→ Arim:是錯的~應該是要由B解A
→ Arim:可以去看計算理論的書~應該比一般演算法的書解釋的清楚吧