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?
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With