This post assumes an undergraduate level of computer science engineering education. Basic familiarity with concepts such as Turing machines, P, NP, NP-completeness, decidability, and undecidability is also assumed. The reader is always encouraged to contact me in the comments or via email if there is anything they need to be clarified. Without further ado, let's dive in.

## 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.

Therefore, we must develop principled approaches and techniques to solve new and unseen problems. Here is the good part - most unsolved problems we encounter already have some relation to some existing problem. This relation to solved problems is something that we can now prod and prick incessantly and eventually use to arrive at a conclusion about the new problems. While hardly elegant in its conception, this approach is extremely sophisticated in its execution. This is the basis for the mathematical technique known as reduction.

## When can we use reduction techniques?

Take two problems, $O$ (an old problem) and $N$ (a new problem). Consider the two following situations that might arise where we would ideally like to avoid reinventing the wheel.

- We know that $O$ is
*easy*to solve, and we notice that the underlying mathematical structure of $N$ is similar to $O$. - We know that $O$ is
*hard*to solve, and once again, $N$ is similar to $O$.

*Mathematically we say that $N\subseteq O$ or $N$ reduces to $O$*.

In the second case, we can again exploit the structural similarities, but this time to a different end. Without prior context, it is difficult to show that $N$ is hard to solve. Therefore, we start with the assumption that $N$ is easy to solve. Now exploiting the similarities between $O$ and $N$, we transform all instances of $O$ to some instance of $N$. This gives rise to a contradiction. We have apparently shown that $O$ reduces to $N$, but we can prove that $O$ is hard to solve. Therefore $N$ has to be hard to solve as well. Otherwise, we could use the algorithm for $N$ to solve for $O$.

Let us explore a few properties of reductions now.

## Remarks on reductions

**Relative Hardness**If $A\subseteq B$, then $B$ is at least as hard as $A$ to solve, i.e., $A$ cannot be harder to solve than $B$.

**Reductions as relations**

- Trivially $A\subseteq A$ by using identity transformations. Therefore reductions are reflexive relations.
- If $A\subseteq B$ and $B\subseteq C$ then we can prove that $A\subseteq C$ by composing the transformations. Therefore reductions are transitive relations.
- Reductions are, however, not symmetric relations (and, therefore, by extension, not equivalence relations).

As stated earlier, if $A\subseteq B$, then $B$ is at least as hard or harder to solve than $A$. Therefore, $A\subseteq B$ does not imply $B\subseteq A$. A concrete example of this was discussed: We can reduce SAT, which is a decidable problem, to the Halting problem, which is an undecidable problem, but the converse is not true.

## Formalizing reductions

*Only the construction*of the reduction method $R$ needs to be efficient, and solving $O_B(R(x))$ does not need to be efficient.

- Our input $x$ is the SAT formula.
- We construct a TM $T$ which accepts $x$ and does the following:
- $T$ iterates over all possible assignments to find a satisfying assignment.
- If $T$ finds a satisfying assignment, it will halt.
- Otherwise, we put $T$ into an infinite loop.
- Our reduction $R(x)$ takes the SAT formula and returns an encoding of $T$ with $x$. More precisely, we have something like $R(x)=\left<\lfloor T\rfloor,x\right>$.
- We pass $R(x)$ to $O_{\text{halt}}$.
- If $O_{\text{halt}}$ returns yes, this implies $T$ halts on input $x$, which in turn implies $x$ has a satisfying assignment. Therefore $R(x)\in\text{HALT}\implies x\in\text{SAT}$.
- If $O_{\text{halt}}$ returns no, then $T$ does not halt on input $x$, which implies that $x$ does not have a satisfying assignment. Therefore $R(x)\notin\text{HALT}\implies x\notin\text{SAT}$. We can take the contrapositive of this expression to obtain $x\in\text{SAT}\implies R(x)\in\text{HALT}$.

## Taxonomy of **Polynomial-time **reductions

### Karp Reductions / poly-time Many-one reductions

**perform only one oracle call**to $O_B$. The earlier reduction from SAT to HALT was a Karp reduction.

- For example, in
*logspace many-one reductions,*we can compute $R(x)$ using just logarithmic space instead of polynomial time. - Even more restrictive notions of reductions consider reductions computable by constant depth circuit classes.

### Truth Table Reductions

**constant ($k$) number of oracle calls**to $O_B$.

- $A$: What is the minimum sized independent set for $G$?
- $B$: Does $G$ have an independent set of size $k$?

### Cook Reductions / poly-time Turing Reductions

**polynomial number of oracle calls**and polynomial time for transforming the inputs. These are the most general form of reductions, and the other forms of reductions are restrictions of Cook reductions. In the example graph $G$ used for TT reductions, if we assume the number of vertices of $G$ to be a polynomial, then the reduction $A\subseteq B$ using the same exact process would be a Cook reduction.

**Aside:**From the nature of the examples, we can see that Karp reductions only extend to decision problems (problems with yes/no outputs). In contrast, Cook reductions can accommodate search/relation/optimization problems (problems with a set of outputs).

## Basic reductions in Computability Theory

- If $A$ is decidable, what can we say about $B$?
- If $A$ is semi-decidable, what can we say about $B$?
- If $A$ is undecidable, what can we say about $B$?

**Note:**The reduction function must itself be a computable function.

- If $B$ is decidable, $A$ is decidable.
- If $B$ is semi-decidable, $A$ is semi-decidable.
- If $A$ is not decidable, then $B$ is not decidable.
- If $A$ is not semi-decidable, then $B$ is not semi-decidable.
- $A\subseteq B$, then $\bar{A}\subseteq \bar{B}$, where $A$ and $B$ are decidable problems.

## Notions of reductions in Complexity Theory

**P**,

**NP,**and

**PSPACE**are

*closed*under Karp and logspace reductions. The complexity classes $L$ and $NL$ are

*closed*only under logspace reductions. Closure has the following semantics - given a problem $A$ in a complexity class

**C**, any problem $B$ such that $B\subseteq A$ is also in

**C**.

### Completeness

**C**which is closed under reduction $r$, if there exists a problem $A$ in

**C**such that all other problems in

**C**are $r$-reducible to $A$, $A$ is said to be

**C-complete**.

**NP-complete**problem is in

**NP,**and all problems in

**NP**are Karp-reducible to it. The notions of PSPACE-completeness and EXPTIME-completeness are similarly defined under Karp-reductions.

**P-completeness**. Consider any non-trivial decision problem in P (trivial problems are akin to constant functions). Every other non-trivial decision problem is Karp-reducible to it. Therefore every non-trivial decision problem is

**P-complete**under Karp-reductions. This definition is essentially the same as P (minus the empty language and $\Sigma^*$). Under Karp-reductions, the notion of

**P-completeness**is semantically useless. Therefore, we use weaker forms of reductions such as logspace reductions or reductions using constant depth circuit computable functions to achieve a more meaningful notion of

**P-completeness**.

### Self reducibility

Decision problems are yes/no problems where we ask if a solution exists. However, sometimes we also want to solve the corresponding search problem to find a solution (if one exists).

In the context of languages in **NP**, self-reducibility essentially states that if we can efficiently solve the decision version of a problem, we can also efficiently solve the search/optimization version of the problem. A more formal definition would be as follows - the search version of a problem *Cook-reduces* (polynomial-time Turing-reduces) to the decision version of the problem. Every **NP-complete** problem is self-reducible and downward self-reducible.