Computer Science › Algorithms & Software
The claim — not a theorem, a thesis — that anything intuitively "computable" by any mechanical procedure at all can be computed by a Turing machine, and why this quietly settles what "algorithm" even means.
An infinite tape, a read/write head, and a table of rules — just enough mechanics to define precisely what it means for a machine to accept, reject, or loop forever on an input.
The class of problems solvable in polynomial time — a precise, formal home for the Big-O vocabulary already covered, and the standard, if imperfect, dividing line between "efficiently solvable" and "not."
Not "exponential time" — the class of problems whose SOLUTIONS can be checked in polynomial time, even if no one knows how to find one quickly, and why P is provably contained inside it.
A problem is NP-complete when it's both in NP and at least as hard as every other problem in NP — and the Cook-Levin theorem's real, historic payoff: at least one such problem (SAT) provably exists at all.
Once one NP-complete problem is known, proving a new one is NP-complete never requires repeating Cook-Levin's argument — a polynomial-time reduction from an already-known NP-complete problem is enough.
NP is built to verify a YES answer quickly — coNP is its mirror image, built to verify a NO answer quickly instead — and whether the two classes are actually the same is a real, still-open question in its own right.
A full polynomial-time reduction from Hamiltonian Cycle proves TSP's decision version is NP-complete, a sharp contrast with Minimum Spanning Trees, which looks superficially similar but is solved exactly in polynomial time by Kruskal's and Prim's algorithms.
A machine that halts and correctly answers yes-or-no on every input DECIDES a language — one that halts and says yes on every string that belongs, but may loop forever on ones that don't, only RECOGNIZES it, and the gap between these two is not a technicality.
No algorithm can decide, for every possible program and input, whether that program eventually halts — Turing's original diagonalization argument, structurally a proof by contradiction, proved here in full, and shown to be recognizable but not decidable.
Proving a new problem undecidable without repeating the diagonalization argument from scratch — by showing that solving it would let you solve the Halting Problem, which is already known to be impossible.
Every non-trivial question about what a program's behavior actually DOES (not how it's written) is undecidable — a single, sweeping theorem that instantly settles an entire universe of "is this decidable?" questions at once.
The single most famous open problem in computer science — does every problem whose solution can be checked quickly also admit one that can be FOUND quickly — and why a resolution either way would upend cryptography and optimization overnight.
Part of the Computer Science curriculum.
The claim — not a theorem, a thesis — that anything intuitively "computable" by any mechanical procedure at all can be computed by a Turing machine, and why this quietly settles what "algorithm" even means.
An infinite tape, a read/write head, and a table of rules — just enough mechanics to define precisely what it means for a machine to accept, reject, or loop forever on an input.
The class of problems solvable in polynomial time — a precise, formal home for the Big-O vocabulary already covered, and the standard, if imperfect, dividing line between "efficiently solvable" and "not."
Not "exponential time" — the class of problems whose SOLUTIONS can be checked in polynomial time, even if no one knows how to find one quickly, and why P is provably contained inside it.
A problem is NP-complete when it's both in NP and at least as hard as every other problem in NP — and the Cook-Levin theorem's real, historic payoff: at least one such problem (SAT) provably exists at all.
Once one NP-complete problem is known, proving a new one is NP-complete never requires repeating Cook-Levin's argument — a polynomial-time reduction from an already-known NP-complete problem is enough.
NP is built to verify a YES answer quickly — coNP is its mirror image, built to verify a NO answer quickly instead — and whether the two classes are actually the same is a real, still-open question in its own right.
A full polynomial-time reduction from Hamiltonian Cycle proves TSP's decision version is NP-complete, a sharp contrast with Minimum Spanning Trees, which looks superficially similar but is solved exactly in polynomial time by Kruskal's and Prim's algorithms.
A machine that halts and correctly answers yes-or-no on every input DECIDES a language — one that halts and says yes on every string that belongs, but may loop forever on ones that don't, only RECOGNIZES it, and the gap between these two is not a technicality.
No algorithm can decide, for every possible program and input, whether that program eventually halts — Turing's original diagonalization argument, structurally a proof by contradiction, proved here in full, and shown to be recognizable but not decidable.
Proving a new problem undecidable without repeating the diagonalization argument from scratch — by showing that solving it would let you solve the Halting Problem, which is already known to be impossible.
Every non-trivial question about what a program's behavior actually DOES (not how it's written) is undecidable — a single, sweeping theorem that instantly settles an entire universe of "is this decidable?" questions at once.
The single most famous open problem in computer science — does every problem whose solution can be checked quickly also admit one that can be FOUND quickly — and why a resolution either way would upend cryptography and optimization overnight.