Reductions

Mathematical Logic · Axiom Academy

A powerful technique for proving undecidability Mathematical Logic • Unit 6 - Computability Theory A reduction is a transformation that converts one problem into another. If we can solve problem B, then we can use that solution to solve problem A by reducing A to B. Informal Definition: Reduction Problem A reduces to problem B if we can transform any instance of A into an instance of B such that: The transformation is computable The answer to A equals the answer to B The Decidability Transfer Theorem Reductions allow us to transfer decidability from one problem to another. This is the foundation of using reductions. Theorem: Decidability via Reduction If and B is decidable, then A is decidable. Proof idea: Use the decider for B to build a decider for A by first reducing A to B. Decidability flows "backward" along reductions: If we know B is decidable and A reduces to B, we learn that A is decidable too. This gives us a systematic way to prove decidability: Find a known decidable problem B The Contrapositive: Proving Undecidability The real power of reductions comes from the contrapositive of our theorem. This is how we prove problems are undecidable! Contrapositive: Undecidability via Reduction If and A is undecidable, then B is undecidable. Standard Technique for Proving Undecidability To prove problem B is undecidable: Start with a known undecidable problem A Conclude that B must be undecidable

This is the written version of the interactive lesson above. See the full Mathematical Logic course.