How to determine the polynomial runtime of an NP reduction?

Question

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?

Answer 1

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:

1. $\Pi \in$ NP, and
2. $\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.