We're sorry but this app doesn't work properly without JavaScript enabled. Please enable it to continue.

This lesson's interactive features are locked, please to keep using them

The Negative Case

We do not know for sure if P equals NP because we can't find any polynomial-time solutions to NP-complete problems. Additionally, we have been unable to prove whether P does not equal NP. We suspect P does not equal NP because it has been so difficult to prove that P = NP.

That said, it's actually more complicated to prove the negative case. To prove the positive case, that P = NP, we simply need to solve an NP-complete problem like TSP in polynomial time. In order to prove the negative case, that P != NP, we would need to exhaustively prove that there's no possible way to solve TSP in polynomial time. That's a lot trickier.