3 ms·
To prove that P does not equal NP you would have to prove that a problem thought to be NP Complete was in fact NP Intermediate. That is, the problem meets the
by nsnick 11y ago
To prove that P does not equal NP you would have to prove that a problem thought to be NP Complete was in fact NP Intermediate. That is, the problem meets the conditions of NP, but NP Complete problems cannot be reduced to it.
- Ar-Curunir 11y agoNo, not really. There are many NP-Complete problems, and there are many NP problems that are thought to be neither NPC nor in P. In fact, if P != NP, there are infinitely many such problems. So proving P != NP could proceed by finding some problem in NP that is not also in P.
- nsnick 11y agoWhich problem do you think is NP but is not NP Complete?
- Ar-Curunir 11y agoSee: https://en.wikipedia.org/wiki/NP-intermediate https://en.wikipedia.org/wiki/NP-intermediate
- nsnick 11y agoGreat link I particularly like the part that says, "P = NP if and only if NPI is empty." seems to indicate that if there are any NP Intermediate problems P would be proven not to equal NP.
- mnarayan01 11y agoThat's pretty far from your original statement. Which isn't to say that's not what you _meant_ in your original statement; just that it's not how I (and minimally the GP) read it.