Complexity

An exponential speedup for factoring and discrete log, killing RSA and ECC; and only a square root for unstructured search, which is why symmetric crypto survives...

Convince someone you know a secret while revealing nothing. The most counterintuitive constructive result in the series.

All of modern crypto rests on an unproven assumption. Why P != NP would still not be enough to secure anything.

A named theory result sitting in the middle of every compiler backend, plus why the NP-hardness does not stop anyone. Part V's counterweight to all the type theory.

Interaction plus randomness lets a prover convince you of things you could never check alone.

Randomness probably doesn't add power; the surprise is that hardness is what buys you fake randomness.

Beyond P vs NP: why your O(n^2) string algorithm is probably optimal too.

An actual, unconditional circuit lower bound. Proof that lower bounds are possible at all, which is what stops The barriers: relativization and natural proofs from...

"NP-hard" hides that some hard problems are easy when one parameter is small. The most practically useful refinement of Karp's 21 problems.

The positive side: 2-approximate vertex cover, PTAS, and where the approximability cliff sits.

Every proof can be checked by reading three bits, and therefore some problems are hard even to approximate.

Why P vs NP has resisted for fifty years, stated as two theorems about which proof techniques cannot work.

Thousands of unrelated-looking problems are secretly the same problem.

SAT is NP-complete: circuits encode computation. The technical heart of the whole field.

Verifying vs finding. State it properly, including what a proof either way would actually change.

"Solve A by solving B" is how undecidability and hardness both spread. The mechanical skill behind Parts II and IV.