the time hierarchy theorem
Almost every separation in complexity theory is an open conjecture, but the hierarchy theorems are the rare, hard-won exceptions where we can actually PROVE more resource buys more power. The time hierarchy theorem says it for steps: give a machine genuinely more time and it can decide strictly more languages. There are problems solvable in n^3 time that simply cannot be solved in n^2 time, no clever trick will close the gap. It is the bedrock guarantee that the time ladder really does climb.
Formally (one clean version), if f and g are well-behaved (time-constructible) functions and f grows enough faster than g, specifically g(n) times log g(n) is o(f(n)), then TIME(f(n)) strictly contains TIME(g(n)). The proof is diagonalization with a clock. Build a machine D that, on input the code of a machine M, simulates M on its own code for f(n) steps using a counter as a stopwatch; if M halts and accepts within the budget, D rejects, and otherwise D accepts. Then D's language differs from every machine that runs within the smaller bound, on that machine's own description, exactly Cantor's diagonal argument, now timed. The small log factor is the overhead of the universal simulation keeping track of the clock.
The payoff is a chain of genuine separations: P is strictly contained in EXPTIME, for instance, is a theorem, not a conjecture, because exponential time is more than any single polynomial. So there really are problems that are decidable but provably require exponential time, an infinite ladder of harder and harder problems. Caveat to keep honest: the theorem separates classes that differ by more than a logarithmic factor, so it does NOT settle close-by questions like P versus NP (those are not a pure 'more of the same resource' gap, they involve nondeterminism). It tells us the ladder climbs, but not how two different kinds of ladders compare.
A concrete consequence: TIME(n) is strictly inside TIME(n^2 log n), so some language can be decided in roughly quadratic time but not in linear time. Pushed all the way, since every polynomial n^k is eventually beaten by 2^n, we get P strictly inside EXPTIME: there exist decidable problems that provably need exponential time.
Diagonalize with a clock: a faster machine decides strictly more languages, so the time ladder truly rises.
It separates classes that differ by more than a small (logarithmic) factor, so it proves P is strictly inside EXPTIME but says NOTHING about P versus NP, which is a different-resource (nondeterminism) gap, not pure 'more time'.