9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Joe Oct 3 '12 at 18:05
  • $\begingroup$ If the problems are not both in the same complexity class, then there may not be a reduction both ways. $\endgroup$ – Joe Oct 3 '12 at 18:07
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why does such a reduction mean that B is not easier than A though? UV for effort, but too abstract for my puny brain. $\endgroup$ – The Unfun Cat Oct 1 '12 at 21:05
  • $\begingroup$ 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... $\endgroup$ – The Unfun Cat Oct 1 '12 at 21:17
  • $\begingroup$ @TheUnfunCat (updated with 3 and 4-coloring example) $\endgroup$ – jmad Oct 1 '12 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.