P vs NP Problem
← Back to Complexity Classes
The most important open question in computer science: does every problem whose solution can be verified in polynomial time also have a polynomial-time solution? One of the seven Millennium Prize Problems with a $1 million bounty.
Key Properties
Related
- P (one side of the question)
- NP (the other side)
- NP-Complete (if any NPC problem is in P, then P = NP)