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

  • $\begingroup$ Thank you for your answer. My problem was exactly the point you make in you second sentence. I guess the point is that you do not get a satisfying assignment, but you "just" solve the decision problem. $\endgroup$ – tex Jun 7 '12 at 11:06
  • $\begingroup$ @tex: Going by your comment I'm not sure my post really answered your question. Please see my edit. $\endgroup$ – Rahul Jun 8 '12 at 18:30

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.