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)


(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.

  • 1
    $\begingroup$ Note that showing that 4-colourability is in NP is as easy as showing the same for 3-colourability: "guess" a colouring and check it's proper. (Or, to put it another way, a colouring is a polynomially bounded certificate.) $\endgroup$ – David Richerby Feb 4 '15 at 16:00

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.