

0 / 2 embers
0 / 3000 xp
click for more info
Complete a lesson to start your streak
click for more info
Difficulty: 3
click for more info
Not enough gems
Cost: 6 gems
1: NP
incomplete
2: Traveling Salesman Problem
incomplete
3: Verify TSP
incomplete
4: TSP Review
incomplete
5: NP-Complete
incomplete
6: Verifying Solutions
incomplete
7: Does P Equal NP?
incomplete
8: The Negative Case
incomplete
9: NP-Hard
incomplete
10: Prime Factorization
incomplete
11: Prime Factoring Review
incomplete
12: Prime Factoring Review
incomplete
13: Subset Sum Problem
incomplete
Back
ctrl+,
Next
ctrl+.
This lesson's interactive features are locked, please to keep using them
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.