reductions

This post assumes basic familiarity with Turing machines, P, NP, NP-completeness, decidability, and undecidability. The reader is referred to the book by Sipser, or the book by Arora and Barak for any formal definitions that have been skipped in this post. Without further ado, let’s dive in. Introduction In an earlier post, we familiarised ourselves with the notion of reductions. Towards the end, we introduced the notion of self-reducibility which is our main topic of focus today....

This post assumes basic familiarity with Turing machines, P, NP, NP-completeness, decidability, and undecidability. The reader is referred to the book by Sipser, or the book by Arora and Barak for any formal definitions that have been skipped in this post. Without further ado, let’s dive in. Introduction The What and Why of 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!...