# Hardness and directions of reductions

Let us say we know that problem A is hard, then we reduce A to the unknown problem B to prove B is also hard.

As an example: we know 3-coloring is hard. Then we reduce 3-coloring to 4-coloring. By conflating one of the colors in the 3-coloring you have a 4-coloring, ergo 4-coloring is hard.

That's the how. But why is this a proof that 4-coloring is hard? Is it that you can use the solution to the 4-coloring problem to solve the 3-coloring problem? If so, how? If not, why is it a valid proof?

Bonus q: Must the polynomial reductions be able to go in both ways?

Edit: if you would be able to explain why this is so by an example you would do the internet a favor. I couldn't find this explained in a concrete way anywhere.

• If you are dealing with two NP-complete problems, then yes, there must be polynomial reductions that go in both ways. In many cases, the reductions from A to B and from B to A may look very different from each other. – Joe Oct 3 '12 at 18:05
• If the problems are not both in the same complexity class, then there may not be a reduction both ways. – Joe Oct 3 '12 at 18:07

A reduction from a problem $A$ to another problem $B$ is a transformation $f$ of any instance $a$ of $A$ into an instance $f(a)$ of $B$, such that

$$\qquad\qquad x∈A ~~⇔~~ f(x)∈B \qquad \qquad (E)$$

If $f$ is a transformation preserving the complexity you are interested in (e.g. $f$ is a polynomial transformation if you consider $\mathsf{NP}$-hardness) then the existence of an algorithm $\mathcal A_B$ solving $B$ implies the existence of an algorithm solving $A$: it is enough to run $f$, then $\mathcal A_B$.

Hence the existence of such a reduction from $A$ to $B$ means that $B$ is not easier than $A$. It is not necessary to have a reduction the other way.

For example, for graph coloring. You can reduce 3-coloring to 4-coloring but not in the immediate way. If you take a graph $G$ and you choose $f(G)=G$ then you will have that $x∈3\mathsf{COL}$ $⇒$ $f(x)∈4\mathsf{COL}$ but you don't have $f(x)∈4\mathsf{COL}$ $⇒$ $x∈3\mathsf{COL}$ of course. The conclusion is that the equivalence $(E)$ is not respected, so $f$ is not a reduction.

You can build a correct reduction $f$ from $3\mathsf{COL}$ to $4\mathsf{COL}$ but it is a little more complicated: for any graph $G$, let $f(G)$ be the graph $G$ extended with another node $u$ that is linked with an edge to every other node.

• The transformation is complexity-preserving (polynomial, here);
• if $G$ is in $3\mathsf{COL}$ then $f(G)$ is in $4\mathsf{COL}$: just use the fourth color for $u$;
• if $f(G)$ is in $4\mathsf{COL}$ then you can prove that all the nodes except $u$ have a color that is not $u$'s, hence $G$ is in $3\mathsf{COL}$.

That proves that $f$ is a reduction and that $4\mathsf{COL}$ is harder than $3\mathsf{COL}$. You can prove the same way that $n\mathsf{COL}$ is harder than $m\mathsf{COL}$ for any $n≥m$, the interesting proof being of the fact that $3\mathsf{COL}$ is harder than any $n\mathsf{COL}$.

• Why does such a reduction mean that B is not easier than A though? UV for effort, but too abstract for my puny brain. – The Unfun Cat Oct 1 '12 at 21:05
• Is it that the answer will be the same for B as for A after you have reduced A to B? I think I got it: if the original instance has a three coloring, then the transformed instance will have a four-coloring so if the answer is "yes, it does have a four coloring", the answer is also "yes, it has a three coloring"? But isn't it still possible that the transformed instance B has a four-coloring without A having a three-coloring? I imagine it is easier to color a graph with four colors... – The Unfun Cat Oct 1 '12 at 21:17
• @TheUnfunCat (updated with 3 and 4-coloring example) – jmad Oct 1 '12 at 21:58