Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Can NP-Intermediate exist if P = NP?

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?

like image 243
Jason Baker Avatar asked Jan 23 '23 06:01

Jason Baker


1 Answers

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.

like image 140
Michael Madsen Avatar answered Feb 24 '23 16:02

Michael Madsen