Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

6
  • $\begingroup$ I believe you, but why do I get $P \leq_p Q$ for free? There is just some existence (and not constructive) proof right? $\endgroup$ Commented Dec 12, 2014 at 10:51
  • $\begingroup$ It's because of the Cook-Levin theorem, which is constructive (to some degree). A problem is in $NP$, if there exists a polynomially verifiable certificate (informally: we can check whether a potential answer is correct with a polynomial algorithm). Cook-Levin shows how to encode this polynomial verification algorithm as a polynomial size 3-SAT formula, and then (by quantifying over the certificate in the formula) that the original problem can be reduced to 3-SAT. $\endgroup$ Commented Dec 12, 2014 at 10:54
  • $\begingroup$ Ok, so here $X$ be some routine for solving an arbitrary polynomial size 3SAT formula in polynomial time. How in practice does one now solve an arbitrary 3-coloring problem in polynomial time? I can believe that perhaps such a routine must exist, but do we have to do a lot of work to find the routine? $\endgroup$ Commented Dec 12, 2014 at 11:00
  • $\begingroup$ In theory, you would apply the Cook-Levin theorem to your 3-coloring instance and transform it to an equivalent, polynomial size 3-SAT problem which you then solve in polynomial time using $X$. In practice you wouldn't use Cook-Levin because it increases the problem size dramatically (a $\Theta(n)$ size 3-coloring instance would get transformed to a $\Theta(n^3)$ size 3-SAT instance) and you would need to come up with a cleverer reduction. The Cook-Levin theorem constructs a polynomial reduction, but is not very efficient (but you usually don't care about efficiency when showing hardness). $\endgroup$ Commented Dec 12, 2014 at 11:05
  • $\begingroup$ Fantastic. So the Cook-Levin theorem always lets us use the verification method for a solution to "cook" a 3SAT instance, and only requires of us that some problem $A$ is in $NP$ and that $3SAT \leq_p A$ (or $B \leq_p A$ where $3SAT \leq_p B$ was shown elsewhere)? $\endgroup$ Commented Dec 12, 2014 at 11:10