A complete, source-aware course

Understand complexity. Do not just memorize proofs.

A bilingual path from computation theory to NP-completeness, approximation, randomness, and space complexity—with explanations, solutions, and interactive visuals.

Start learning Browse exercises Statements

362 PDF + 4 books

Source map with page-level references

11 units

From foundations through PH and oracles

HE ⇄ EN

A complete mirrored path in both languages

Course map

Each topic builds on the previous one with precise definitions, intuition, proofs, and practice.

Your progress0 of 11

Not startedPrerequisitesComputability, logic, graphs, asymptotics, and probability.
Not startedModels and resourcesTuring machines, configurations, time, and space.
Not startedDeterministic classesDTIME, DSPACE, hierarchy theorems, and core inclusions.
Not startedNondeterminismComputation trees, NTIME/NSPACE, simulation, and padding.
Not startedNP and coNPWitnesses, verifiers, complements, and open questions.
Not startedReductions and completenessKarp reductions, NP-hardness, and Cook–Levin.
Not startedCanonical problemsSAT, graph, number, path, and coloring problems.
Not startedOptimization and approximationApproximation ratios, Vertex Cover, Max-Cut, TSP, and Bin Packing.
Not startedRandomizationRP, BPP, amplification, Freivalds, and Karger.
Not startedSpace complexityL, NL, Savitch, log-space reductions, and coNL.
Not startedAdvanced structureThe polynomial hierarchy, oracles, and relativized classes.