Come determinare il tempo di esecuzione polinomiale di una riduzione di NP?

Question

Per mostrare che un problema NP è NP-completo, dobbiamo anche dimostrare che $ L \ leq_ {p} L '$, dove $ L $ è dimostrato NP-completo e si deve dimostrare $ L' $ anche è. La cosa che mi sono confuso è come in tutti i problemi NP-completi in CLRS hanno appena affermano l'algoritmo di riduzione a $ L $ per convertire a $ L '$ è polinomiale. Come si può dimostrare che è tempo polinomiale, fornito un esempio come una cricca o prosciutto ciclo tipo di problema?

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.