0

I just have a quick question. If we have two decisions problems, say L1 and L2. If L1 and can be reduced to L2 in polynomial time, then is it true that L2 CANNOT be reduced to L1 in polynomial time?

My understanding is that this would mean:

L1 can be reduced to L2 in polynomial time => NOT (L2 can be reduced to L1 in polynomial time)
=(L1 not in P) & (L2 in P) => (L1 in P) & (L2 not in P)
=[(L1 in P) OR (L2 not in P)] OR [(L1 in P) & L2 in P)]
=(L1 in P) OR (L2 not in P)

So the statement that L1 can be reduced to L2 in polytime implies that L2 cannot be reduced to L1 in polytime is only true if L1 is in P or if L2 is not in P. As in there, if that is not the case, then the statement is false.

Does my logic make sense or am I way off? Any advice or help would be much appreciated. Thank you!

4

1 回答 1

1

一般陈述“如果 L 1多时间减少到 L 2，则 L 2不会减少到 L 1 ”通常是错误的。P 中的任何两个问题（除了 ∅ 和 Σ*）都是多时间可相互约简的：只需在多项式时间内解决问题，并根据需要输出是或否的答案。

您的特定逻辑不正确，因为两个问题之间的多项式时间可简化性并不能保证语言是否在 P 中。例如，停止问题是多项式时间可简化为 TM 是否接受给定字符串的问题，但两个问题都不存在于 P 中，因为这两个问题都不可判定。

希望这可以帮助！

于 2013-11-01T03:28:43.990 回答