To show that a NP problem is NP-complete, we also have to show that $L \leq_{p} L'$ , where $L$ is proven NP-complete and you have to prove $L'$ also is. The thing I am confused is how in all NP-complete problems in CLRS they just state the reduction algorithm for $L$ to convert to $L'$ is polynomial. How can one prove it's polynomial time, provided an example such a clique or ham cycle kind of problem?
$\begingroup$
$\endgroup$
-
$\begingroup$ "... they just state ...": are you sure? In many books the polynomial runtime of the "common" reductions are explained (more or less formally, often giving a bound on the size of the "gadgets" used in the reduction). $\endgroup$ – Vor Dec 1 '12 at 17:32
$\begingroup$
$\endgroup$
The problem here is a misunderstanding of the point of the reduction. NP-complete problems are not known to have polynomial time algorithms. If they do, then P $=$ NP, if they don't then P $\neq$ NP - this is the BIG question of theoretical computer science.
The point of the reductions you're looking at is to show that the problem $L'$ is NP-complete, and thus at least as hard as anything else in NP. It does this by demonstrating that if you could solve $L'$ in polynomial time, then using the reduction you could solve $L$ in polynomial time too (take the instance of $L$, convert it to an instance of $L'$, solve that, then use that solution to get the solution to the original instance).
As $L$ is NP-complete, this also means that if we could solve it in polynomial time, we could solve every problem in NP in polynomial time (hence the intuition that NP-complete problems are in some sense the "hardest" problems in NP).
Just to add some technical bits on top of that, a problem $\Pi$ is NP-complete if:
- $\Pi \in$ NP, and
- $\Pi$ is NP-hard.
A problem $\Pi$ is in NP if there is an non-deterministic algorithm that solves $\Pi$ in polynomial time in the size of the input or equivalently we can check an answer to an instance of $\Pi$ in deterministic polynomial time.
A problem $\Pi$ is NP-hard if for every problem $\Phi \in$ NP, there exists a polynomial time reduction such that $\Phi \leq_{p} \Pi$ (this can be a different reduction for each $\Phi$). In practice what we do is actually chain these reductions together, so say we have an NP-hard problem $\Pi'$, then we know that there's reductions from everything in NP to it, so if we can show that $\Pi' \leq_{p} \Pi$ then by composing the reductions, we can show that there's a reduction from everything to $\Pi$ (we just go via $\Pi'$).
So just to come back to the original question, we don't know if there's a polynomial time algorithm for $L'$ - most(?) people would probably suspect that there isn't, as lots of people have spent lots of time trying to find even one polynomial time algorithm for any NP-complete problem and there's been no luck so far (of course such an algorithm for any of them means a polynomial time algorithm for everything in NP). The reduction 'just' shows that $L'$ is one of these hard problems.
answered Dec 1 '12 at 5:51
-
$\begingroup$ I think the OP asks how to show the reduction runs in polynomial time, not the problem. $\endgroup$ – Raphael♦ Dec 1 '12 at 14:07
-
$\begingroup$ @Raphael, that'd make a lot more sense than what I was thinking. It's too hot today. 33C/94F is just the wrong weather for thinking. $\endgroup$ – Luke Mathieson Dec 1 '12 at 14:28
-
$\begingroup$ Haha, been there. You should come over, we have just above freezing here. :) $\endgroup$ – Raphael♦ Dec 1 '12 at 14:30
