← Algorithm Design learning pathAlgorithm Design · Module 9 of 10
Complexity classes
Understand P, NP and hard problems.
📖 Key ideas
- P: problems solvable in polynomial time.
- NP: solutions verifiable in polynomial time.
- NP-complete: hardest in NP (SAT, TSP decision, 3-colouring).
- NP-hard: at least as hard as NP-complete.
- P vs NP is a famous open problem.
💡 Real-life example: NP problems are jigsaw puzzles: checking a finished puzzle is easy, solving one may take forever.
PSolvable in polynomial time
NPVerifiable in polynomial time
NP-completeHardest problems in NP
ReductionTransforming one problem into another