p-np

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. This is the second part of an earlier post on Self Reductions . Since the two posts are meant to be perused in order, please check out the earlier post for any definitions/concepts not covered in this post....

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 Preliminaries: Search and Decision Problems 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!...