Comment déterminer le temps d'exécution d'une réduction polynomiale NP?

Question

Pour montrer qu'il ya un problème NP est NP-complet, nous devons aussi montrer que $ L \ leq_ {p} L '$, où $ L $ est NP-complet prouvé et vous devez prouver $ L' $ aussi est. La chose que je suis confus est de savoir comment dans tous les problèmes NP-complets dans CLRS ils affirment que l'algorithme de réduction pour $ L $ pour convertir en $ L '$ est polynomiale. Comment peut-on prouver qu'il est temps polynomiale, fourni un exemple d'un tel cycle clique ou jambon genre de problème?

Answer 1

Le problème est une mauvaise compréhension du point de la réduction ici. problèmes NP-complets ne sont pas connus pour avoir des algorithmes polynomiaux. Si elles le font, alors P $ = NP, si elles ne le font pas alors P $ \ neq $ NP -. C'est le BIG question de la science informatique théorique

Le point des réductions que vous cherchez à est de montrer que le problème $ L '$ est NP-complet, et donc au moins aussi fort que toute autre chose dans NP. Il le fait en démontrant que si vous pouviez résoudre $ L « $ en temps polynomial, puis en utilisant la réduction, vous pouvez résoudre $ L $ en temps polynomial trop (prendre l'exemple de $ L $, le convertir en une instance de $ L » $, résoudre que, utilisez cette solution pour obtenir la solution à l'instance d'origine).

$ L $ est NP-complet, cela aussi signifie que si nous pouvions résoudre en temps polynomial, nous pourrions résoudre tous problème dans NP en temps polynomial (d'où l'intuition que le NP-complet les problèmes sont en quelque sorte les problèmes les plus difficiles « dans » NP).

Il suffit d'ajouter quelques morceaux techniques en plus de cela, un problème $ \ Pi $ est NP-complet si:

1. $ \ Pi \ en $ NP et
2. $ \ Pi $ est NP-dur.

Un problème $ \ Pi $ est dans NP s'il existe un algorithme non déterministe qui permet de résoudre $ \ Pi $ en temps polynomial dans la taille de l'entrée ou de manière équivalente, nous pouvons vérifier une réponse à une instance de $ \ Pi $ déterministe polynomiale.

Un problème $ \ Pi $ est NP-difficile si pour tous problème $ \ Phi \ en $ NP, il existe une réduction polynomiale telle que $ \ Phi \ leq_ {p} \ Pi $ (cela peut être une réduction différente pour chaque $ \ Phi $). Dans la pratique ce que nous faisons est une chaîne en fait ces réductions ensemble, donc dire que nous avons un problème NP-dur $ \ Pi « $, alors nous savons qu'il ya des réductions de tout dans NP à, donc si on peut montrer que $ \ Pi » \ leq_ {p} \ Pi $, alors en composant les réductions, on peut montrer qu'il ya une réduction de tout à $ \ Pi $ (nous venons de passer par $ \ Pi '$).

Il suffit donc de revenir à la question initiale, nous ne savons pas s'il y a un algorithme polynomial pour $ L '$ - la plupart des gens se douterait probablement qu'il n'y a pas, comme beaucoup de gens ont passé (?) beaucoup de temps à essayer de trouver même un algorithme polynomial pour tout problème NP-complet et il n'y a pas eu de chance jusqu'à présent (bien sûr un tel algorithme pour l'un d'eux: un algorithme polynomial pour tout NP ). La réduction « juste » montre que $ L '$ est l'un de ces problèmes difficiles.