🧠 P vs NP: Complexity Classes

Understanding the most famous unsolved problem in computer science

NP
P
NP-Complete

The Million Dollar Question: Does P = NP?

If we could prove P = NP, every problem we can quickly verify could also be quickly solved.
Most experts believe P ≠ NP, but no one has proven it.

P (Polynomial Time) Problems solvable in O(nk) time.
"Efficiently solvable."
NP (Nondeterministic Polynomial) Solutions can be verified in polynomial time.
Not necessarily solvable quickly.
NP-Complete Hardest problems in NP.
If any NPC problem is in P, then P = NP.

Example Problems:

Sorting
O(n log n)
In P ✓
Shortest Path
O(E log V)
In P ✓
Primality Test
O(log6 n)
In P ✓
3-SAT
NP-Complete
First proven NPC
Traveling Salesman
NP-Complete
Find shortest tour
Graph Coloring
NP-Complete
k colors, no adj. same