Polynomial-Time Reduction, “at least as hard as”, 3-COLOR and 4-COLOR

Question

The theme is NP-Completeness, I find it hard to grasp the concept of "$A$ is at least as hard as $B$". Why does this mean that we have to reduce $B$ to $A$ and not $A$ to $B$? For me the latter makes a lot more sense. If it takes $n$ steps to solve $B$ and I can change (reduce) $A$ to be exactly like a $B$-problem, then it will take at least $n$ steps to solve $A$ too. Doesn't this mean it is at least as hard as $B$? (Question 1)

I also find it weird that when we want to prove that $A$ is NP-Complete, we reduce an NP-Complete problem $B$ to $A$. Shouldn't it be the other way around? What does it mean if I reduce $A$ to $B$? (Q 2)

The book has a proof that shows why 4-Color is as at least as hard as 3-Color, which shows how to reduce 3-Color to a 4-Color problem. The proof is simply adding a new vertice painted with a new color and connecting this vertice with all other vertices. If I understood correctly, a problem is NP-Complete if it can be reduced to every other NP-Complete problem in polynomial time. This means it should be possible to reduce 4-Color to 3-Color, correct? Wouldn't this also imply that 3-Color is at least as hard as 4-Color? So 3-Color is at least as hard as 4-Color, but 4-Color is also at least as hard as 3-Color (Q 3)

Answer 1

(1) is not true. One way to solve $A$ is to transform it to $B$, and it is longer than $B$, agreed. But perhaps there are other ways of solving $A$ that you have not thought of that are much more optimal? So transforming $A$ into $B$ does nothing to prove that $A$ is intrinsically hard.

The way this is done is, you take a problem $B$ which is already known to be intrinsically hard (i.e. there is no way so solve it easier than $n$ steps) and transform $B$ to $A$. Now, if there was an easy way to solve $A$, you would have an easy way to solve $B$, which is impossible.

(2) Proving NP-completeness needs 2 things:

• The problem can be done in NP. This usually is done by exhibiting an algorithm to solve the problem in NP.
• The problem cannot be done chaper than NP (i.e. is NP-hard). This requires reduction of a known NP-complete problem to your problem (see part 1).

(3) The proof you showed establishes that if I can do 4-color quickly, then I can do 3-color quickly as well, in other words, 4-color is at least as hard as 3-color, and so 4-color is NP-hard. (Since any NP-complete problem can be transformed into 3-color, you showed that 4-color is at least as hard as any NP-complete problem, not just 3-color.)

However, 4-color could still be much harder than 3-color. In other words, if you want to show 4-color is NP-complete, you must also show that it is in NP, e.g. exhibit an algorithm that would determine if a graph is 4-colorable in NP. Together with the proof you wrote it would imply that 4-color is NP-complete.