Decision Problems Reduction in Polynomial Time

Question

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!

Answer 1

The general statement "if L₁ poly-time reduces to L₂, then L₂ does not reduce to L₁" is in general false. Any two problems in P (except for ∅ and Σ*) are poly-time reducible to one another: just solve the problem in polynomial time and output a yes or no answer as appropriate.

Your particular logic is incorrect because polynomial-time reducibility between two problems does not guarantee anything about whether the languages are in P or not. For example, the halting problem is polynomial-time reducible to the problem of whether a TM accepts a given string, but neither problem is in P because neither problem is decidable.

Hope this helps!