Two classes of problems
Complexity theory groups decision problems by how hard they are to solve. Two classes anchor the discussion.
- P contains problems that can be solved in polynomial time, meaning an efficient algorithm finds the answer as input grows.
- NP contains problems whose proposed solutions can be verified in polynomial time, even if finding one might be hard.
Solving versus checking
The crucial distinction is between solving and checking. Given a filled in Sudoku grid you can verify it quickly, but finding the solution from a blank grid feels much harder. NP captures exactly this gap.
- Every problem in P is also in NP, since solving fast implies checking fast.
- A certificate is the candidate solution that a verifier checks in polynomial time.
The open question
Whether P equals NP is one of the deepest unsolved questions in computer science. If they were equal, every problem whose answer is easy to check would also be easy to solve, which would transform cryptography, optimization, and science.
Why most believe they differ
Decades of effort have found no fast algorithm for the hardest NP problems, and much of modern security assumes none exists.
Key idea
P is problems we can solve efficiently and NP is problems whose solutions we can verify efficiently, and whether the two classes coincide remains the central open question of complexity theory.