Reductions & Undecidability

Halting → everything · Rice's theorem

1:00

How to prove a new problem is impossible to solve by translating a known-impossible problem into it — and how the same arrow powers NP-completeness.

By the end, you can

Explain what a many-one reduction A ≤m B is and what it means for the relative difficulty of A and B.
State and apply the undecidability lemma: A undecidable + A ≤m B implies B undecidable.
Identify the correct direction of a reduction for an undecidability proof and explain why the reverse direction proves nothing.
Reconstruct the OUTPUTS-7 reduction — building program N from ⟨M, w⟩ and stating the key equivalence.
State Rice's theorem, define "non-trivial" and "semantic," and apply it to classify properties as decidable or undecidable.
Distinguish semantic (behavioral) questions from syntactic (text-based) questions and predict decidability accordingly.
Explain why perfect virus detection and full program verification are impossible in principle.
Describe how the same reduction technique adapts to prove NP-hardness, noting what changes (map complexity, anchor problem).

Up next in Theory of Computation & Compilers