Theorem

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.

How many errors you can fix given how much you're willing to pay in redundancy.

You can communicate at capacity with arbitrarily low error. Shannon's most surprising result: reliability is free below the limit.

And the proof is an exchange argument you can follow. Opens with Kraft (The Kraft inequality and prefix codes): which length assignments exist at all, then which...

Random placement gives max load ~log n / log log n; picking the emptier of two random bins collapses it to log log n.

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

Four conditions, all necessary for deadlock; break any one. The cleanest example of a characterization theorem doing engineering work.

Any sufficiently strong consistent system has true statements it can't prove, and can't prove its own consistency.

Any program can obtain its own source. Quines aren't a party trick; self-reference is guaranteed by the model.

Four grammar classes, four machine classes, one ladder. Why you can't parse HTML with a regex, stated as a theorem.

One machine simulates all others. Interpreters, VMs, and the stored-program computer are all this one theorem.

Averages of independent things are exponentially unlikely to stray.

Why a dynamic array's O(n) resize is still O(1) per push, and how to prove it rather than hand-wave it.

Lower bounds by playing against the algorithm: finding max and second-max needs n + ceil(log n) - 2 comparisons.

Expectations add even when events are hopelessly dependent. Averaging as an existence proof: if the mean is 5, some input hits 5.

A decision tree with n! leaves must be log(n!) deep, and log(n!) = Theta(n log n) by the (n/2)^(n/2) trick — the one step that costs this post its L1.

Entropy is the exact floor on lossless compression. Where "information" stops being a metaphor.

Collisions arrive at sqrt(N), not N. Sets every hash length, UUID size, and nonce width you will ever choose.