3
$\begingroup$

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.

1 Answers 1

4
  1. $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").

  2. 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.)

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

  • 0
    @tex: Going by your comment I'm not sure my post really answered your question. Please see my edit.2012-06-08