An Introduction to Reductions
This post assumes basic familiarity with Turing machines, P, NP, NP-completeness, decidability, and undecidability. Don’t hesitate to contact me via email if you need further clarification. Without further ado, let’s dive in. Introduction Why do we need reductions? From Archimedes terrorizing the good folk of ancient Syracuse to Newton watching apples fall during a medieval plague, science has always progressed one ‘Eureka!’ at a time. Romantic as these anecdotes may be, for mathematics, we can hardly look to Mother Nature for providing us the key insight to our proofs....