La dureza y las direcciones de las reducciones

Question

Digamos que sabemos que un problema A es duro, entonces reducimos la A a la B problema desconocido para demostrar B también es duro.

A modo de ejemplo: sabemos 3-coloración es difícil. Entonces reducimos 3-coloración de 4-colorear. Al combinar uno de los colores en el 3-coloración tiene un televisor 4-colorear, ergo 4-coloración es duro.

Esa es la forma. Pero ¿por qué es esto una prueba de que el 4-colorante es difícil? ¿Es que se puede utilizar la solución para el problema 4-coloración para resolver el problema 3-coloración? ¿Si es así, cómo? Si no es así, ¿por qué es una prueba válida?

q Bono:? ¿Deben las reducciones polinómicas ser capaz de ir en ambos sentidos

Editar: Si quieres ser capaz de explicar por qué esto es así por ejemplo que haría internet un favor. No pude encontrar esta explicado en una forma concreta en cualquier lugar.

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