作者mqazz1 (无法显示)
站内Prob_Solve
标题[问题] NP的观念
时间Fri Jul 29 20:12:20 2011
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
1F：→ Favonia:hard的精确定义仰赖reduce的精确定义。然後你是用TM吗？ 07/29 20:32
2F：→ Favonia:我的意思是说，允许的reduction恰好是所有O(n)时间演算法? 07/29 20:34
3F：→ mqazz1:这个是研究所的考题 我想可能是比较通俗的定义吧@@? 07/29 20:40
4F：推 shiuantzuo:都不对... 07/30 16:29
5F：推 jfurseteidce:(1)A转成B问题 所以B比A难 (2)藉由解B可以解A 08/11 03:01
6F：推 Arim:第1点应该是要说B至少跟A一样难 第二点是由A解B 08/27 15:47
7F：→ Arim:是错的~应该是要由B解A 08/27 15:48
8F：→ Arim:可以去看计算理论的书~应该比一般演算法的书解释的清楚吧 08/27 15:49