Advanced -> Complexity And Hardness

Reductions, hardness classes, and the language for understanding when exact efficient algorithms are unlikely.

• Topic slug: advanced/complexity-and-hardness
• Tutorial page: Open tutorial
• Ladder page: Open ladder
• Repo problems currently tagged here: 1
• Repo companion pages: 2
• Curated external problems: 5

Microtopics

• reductions
• NP-completeness
• hardness-vs-completeness
• lower-bounds
• P-NP-EXP-BPP
• decision-vs-optimization
• approximation-barriers

Learning Sources

Source	Type
MIT 18.404J Theory of Computation	Course
Computational Complexity: A Modern Approach	Reference
MIT 6.006 Lecture 19 Complexity	Course

Follow-Up Reading

Source	Type
MIT 6.045J	Course

Repo Companion Material

Material	Type
Book Shop note	repo case study
Approximation tutorial	related tutorial

Curated External Problems

Core

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Problem Set 0	Harvard CS221	Theory	-	-	-	Search Vs Decision; Reductions; Complexity Classes	A clean course-quality entry point for formal complexity reasoning.
Problem Set 1	Harvard CS221	Theory	-	-	-	P-Completeness; Circuit Complexity; Factoring	Covers several central reductions and class-separation themes in one place.
Problem Set 3	Harvard CS221	Theory	-	-	-	PSPACE; Branching Programs; Circuit Lower Bounds	Very good practice for moving between models of computation.
Problem Set 4	Harvard CS221	Theory	-	-	-	Promise Problems; #P; Approximation Hardness	Bridges exact complexity language with counting and approximation hardness.
Problem Set 6	Harvard CS221	Theory	-	-	-	PCP; Property Testing; Hardness Of Approximation	A strong advanced capstone on implications, PCPs, and testing/hardness themes.

Repo Problems

Code	Title	Fit	Difficulty	Pattern	Note	Solution
BOOKSHOP	Book Shop	secondary	easy	0 1 knapsack; downward capacity loop; budget value maximization	Note	Code

Regeneration

python3 scripts/generate_problem_catalog.py