A finished jigsaw is instant to verify but agonizing to assemble from scratch. That gap — problems whose answers are quick to check (NP) but seemingly slow to find (P?) — is the heart of the P versus NP question, computing's biggest open mystery.
Easy to check vs. easy to solve
P is the class of problems solvable in polynomial time. NP is the class whose solutions can be verified in polynomial time. Every problem in P is in NP; whether P = NP is the central open question of computer science.
A problem is NP-complete if it's in NP and every NP problem reduces to it. Solve one NP-complete problem efficiently and you solve them all — so none is known to have an efficient algorithm.
- Consider a filled-in Sudoku: is it easy to check it's valid?
- Consider a blank Sudoku: is it easy to solve?
- Match 'check' and 'solve' to verification and search.
What you should see: Checking a solution is fast (NP-style verification); finding one may be hard — the gap that P vs NP is about.