views:

168

answers:

3

My understanding is that Ladner's theorem is basically this:

P != NP implies that there exists a set NPI where NPI is not in P and NPI is not NP-complete

What happens to this theorem if we assume that P = NP rather than P != NP? We know that if NP Intermediate doesn't exist, then P = NP. But can NP Intermediate exist if P = NP?

+3  A: 

You missed one property of NPI: Every element of NPI is in NP (but not in P). This is clearly impossible if P=NP, so if P=NP, NPI must be empty.

sepp2k
+2  A: 

If P=NP, then NPI cannot exist assuming that it is a subset of NP, as all of NP is in P and thus the "not in P" part of the definition of NPI would not hold for any problem. So the class NPI would be empty in that case.

Michael E
+3  A: 

NPI must imply that it is in NP, but that it is not NP-complete.

If P = NP, then all problems in P and NP will be NP-complete, because any problem will be reducible to another one in polynomial time (∅ and Σ* cannot be NP-complete, because we can't map an arbitrary problem to either of them - we won't have anything to map to for the positive/negative case. However, since they are in P, we don't care about them for the purpose of this question.)

Since all problems in NP are NP-complete, NPI cannot exist.

Michael Madsen
So just out of curiosity, why does Ladner's theorem use an "if" rather than an "if and only if"?
Jason Baker
@Jason: That is a good question. Given that it is fairly easy to construct a mapping reduction for any NP problem, such that it runs in polynomial time (assuming P = NP), perhaps he considered the opposite case too trivial to cover. Of course, there's also the possibility that it's merely an oversight and he didn't think about it when he formulated his theorem.
Michael Madsen