Intuitive intro to polynomial time reductions.

The concept of a reduction is fundamental to organising computational problems by relative difficulty. Intuitively, this is useful because if we know problem $A$ to be "hard", and we can establish that problem $B$ is "at least as hard" as $A$, then we know $B$ must also be "hard". This can save a lot of time that could have been spent searching for some fast algorithm for $B$ which may not exist. 

So what is a polynomial time reduction?

Suppose we have two problems $X$ and $Y$. Now suppose that we already know how to solve $Y$ in polynomial time using procedure $P_Y$. If we could construct some procedure, $P_R$, which transforms any instance, $I_X$, of $X$ to an instance, $I_Y$, of $Y$, then we could use our solution to $Y$ to solve $X$ in polynomial time given that:

• $P_R$ runs in polynomial time.
• $I_Y$ as input to $P_Y$ outputs the correct answer for $I_X$.

This is an example of a polynomial reduction from $X$ to $Y$ (written $X \le_P Y$). Intuitively, it helps me to think of this as saying: $X$ is no harder than $Y$, or $Y$ is at least as hard as $X$. Just as relative easiness of a problem can be shown using polynomial reductions, so can relative hardness.

Suppose that there is no polynomial time solution for $Y$. If $Y \le_P X$, then it must be that $X$ is at least as hard as $Y$ and so there is no polynomial time solution for $X$.

Proof. Suppose for contradiction that there exists a polynomial time solution for $X$. Then by the definition of a polynomial time reduction, there would exist a polynomial time solution to $Y$. A contradiction.

Notice that this logic only works if $P_R$ runs in polynomial time.

Snazzy application of pigeonhole principle.

Problem: Prove that a simple graph $G$ with $n > 2$ vertices has at least two vertices with the same degree.

Solution: Notice that there is no guarantee that $G$ is connected. However let us suppose that it is. Then each vertex has degree $d$ where $d \in \{1, 2, ..., n - 1\}$. Since we have $n$ vertices and $n - 1$ degree choices, it must be that at least two vertices in $G$ have the same degree.

This proves the case when $G$ is connected, but what about when it is unconnected?

In this case, each vertex can connect to at most $n - 2$ vertices because for $G$ to be unconnected, there must exist a vertex which is connected to no other vertex. Therefore, each vertex has degree $d$ where $d \in \{0, 1, ..., n - 2\}$. By the same argument used in the connected case, $G$ must have at least two vertices of the same degree.

I thought this was a pretty snazzy approach. There is something so elegant about the pigeonhole principle.