Can NP-Intermediate exist if P = NP?
- by Jason Baker
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?