Hardness and directions of reductions

Question

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.

Answer 1

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}$.