NP-hardness reduction Although I know the notion of polynomial time reduction since many years, I am currently confused about the following problem.
In a reduction from 3-SAT to 3-Coloring, one constructs (in polytime) a graph $G_F$ out of a given 3-CNF formula $F$, s.t. $F$ is satisfiable if and only if $G_F$ is 3 colorable.
In order to show the above "if-part" a typical proof goes like:
" If the graph is 3-colorable, then we can extract a satisfying
assignment from any 3-coloring..." (This sentence is copied form Jeff Ericksons notes, so it must be correct :-) )
Even if we know that a graph is 3 colorable, it is np hard to find any proper 3 coloring. So given $P \neq NP$ this reduction can not be done in polynomial time.
I know that I am making some mistake in the argument above, but I can't currently see where I am wrong.
 A: *

*$P$ and $NP$ are classes of decision problems. You only need to be able to tell whether a given formula $F$ is satisfiable or a graph $G$ is 3-colourable, not to actually produce the satisfying assignment or the colouring (the "witness").

*The reduction itself is not required to find a 3-colouring of the graph $G_F$. You are merely constructing $G_F$ from $F$ in polynomial time, and that's it. The point of the reduction is that if you then had a hypothetical algorithm that could check whether $G_F$ is 3-colourable in polynomial time, you would then immediately know whether $F$ is satisfiable. (Assuming $P \ne NP$, it is impossible to do the latter in polynomial time, so the former must be impossible too.)

*That said, it is often easy to convert a witness of the constructed instance into a witness of the original problem, and that is the case here. If you can find a 3-colouring of $G_F$, the vertex corresponding to each variables must be coloured either $\mathrm{true}$ or $\mathrm{false}$. That gives you a satisfying assignment for $F$.
