I'm reading about the proof that 3-COLOR is in NP-Hard, by reduction of 3-SAT to 3-COLOR (as listed here for example: http://cs.bme.hu/thalg/3sat-to-3col.pdf). And here's a passage from Wikipedia, explaining why this approach works.
There are two main situations where we need to use reductions:
First, we find ourselves trying to solve a problem that is similar to a problem we've already solved. In these cases, often a quick way of solving the new problem is to transform each instance of the new problem into instances of the old problem, solve these using our existing solution, and then use these to obtain our final solution. This is perhaps the most obvious use of reductions.
Second: suppose we have a problem that we've proven is hard to solve, and we have a similar new problem. We might suspect that it is also hard to solve. We argue by contradiction: suppose the new problem is easy to solve. Then, if we can show that every instance of the old problem can be solved easily by transforming it into instances of the new problem and solving those, we have a contradiction. This establishes that the new problem is also hard.
Clearly the second situation applies here.
What I'm wondering í why solving those instances G resulting from reduction of 3-SAT to 3-COLOR is the same as solving all instances of 3-COLOR. In particular, many graphs don't have the same structure as G (i.e. composing of the triangles $BTF$, $BF \cup \text{output node}$, $B{v_i}\bar{v_i}$, and the OR-gadgets), and so don't have a corresponding 3-CNF. If the 3-COLOR problem is about whether a graph with structure similar to G is 3-colorable, then this approach works. But clearly it isn't.
It seems like here there's the implication that every instance of a particular problem is equally hard. At least here in this example, however, we know a lot about the graph G, and it seems to me G could be 3-colored easily and thus the corresponding 3-CNF could be solved easily. But again this doesn't say anything about other graphs that are not like G. Please explain this, and please also correct me here if I seemed to underestimate the difficulty of 3-coloring G.
Best Answer
It's not. The point is to be able to solve just the 3-SAT examples.
Absolutely. But the point of the proof is just to deal with those graphs, specifically.
3-colouring a general such $G$ is indeed hard. In fact, it is exactly as hard as solving 3-SAT!
This sentence in the link is key:
As the second reason in your quote says, we do not care about creating an algorithm for solving 3-colouring. What we care about is showing that it is hard. We do that by showing that if 3-coloring was easy, then 3-SAT must also be easy. But we already know that 3-SAT is not easy. Thus, by contradiction, we must have that 3-coloring was not easy, i.e. it must be hard.
How can we do this? We need to do two things:
Show that any 3-SAT problem can be transformed into a 3-coloring problem in polynomial time. This equivalence is usually the harder part. In this case, one needs to show that, given some instance of a 3-SAT problem, we can get a graph s.t. that graph is 3-colorable if and only if the instance is satisfiable.
Show that if we could magically solve 3-coloring, then we could easily solve 3-SAT.
The second point basically automatically follows from the first, by just transforming a given instance from 3-SAT to 3-color. Do you see where the contradiction comes from? Since an equivalence exists, we can easily/quickly transform between 3-SAT and 3-color. Imagine we had an algorithm $A$ to quickly solve 3-color. But this is impossible, because then the following algorithm quickly solves 3-SAT: (1) transform from $\phi$ to $G$, and (2) use $A$ on $G$.
Notice that we do not need to actually come up with any coloring algorithms, or worry about general graphs and how to color them. We only need to establish a way to get a graph $G$ such that colorability becomes equivalent ("iff") to satisfiability of $\phi$. The proof is then by contradiction.
Note that it doesn't matter how easy or hard $G$ is to color or solve as a 3-color problem instance. It only matters that coloring $G$ tells us the answer to $\phi$, whether positive or negative.
TL;DR: we do not want to try to solve 3-color here, we just want to show we can transform $\phi$ into $G$. (This means if we could solve 3-color then we could solve 3-SAT, but we do not actually want an algorithm to do either of those here.) We can then prove by contradiction that 3-color is hard.
Edits for comments:
About this specific case, I'm not sure. Someone with more graph knowledge could maybe answer. Presumably you mean a poly-time algo. But note that we don't know if $P=NP$. If it does, then there exists an algorithm for all $G$ :)
We don't care about all graphs $X$. We only care about $G$ that arise from 3-SAT. That is sufficient for the proof, since the hardness of those graphs alone is enough (since it is equivalent to 3-SAT). Other graphs don't matter.
This phrase:
No. It's the other way around. The contradiction works if any 3-CNF can be reduced to some equivalent $G$. No other graphs need be considered. I.e., whether or not other graphs can be efficiently colored is unimportant here.
We don't need to generalize it. This fact alone is sufficient for the proof. Since these $G$ graphs are a subset of $X$, and just solving them alone is hard, clearly solving $X$ is equally hard or harder.