[algorithm] Quelles sont les différences entre NP, NP-Complet et NP-Hard?


Answers

J'ai regardé autour de moi et j'ai vu de nombreuses longues explications. Voici un petit tableau qui peut être utile pour résumer:

Remarquez comment la difficulté augmente de haut en bas: tout NP peut être réduit à NP-Complet , et n'importe quel NP-Complet peut être réduit à NP-Hard , tout en temps P (polynomial).

Si vous pouvez résoudre une classe de problème plus difficile en temps P, cela signifie que vous avez trouvé comment résoudre tous les problèmes plus faciles en temps P (par exemple, prouver P = NP, si vous trouvez comment résoudre n'importe quel problème NP-Complet dans P heure).

____________________________________________________________
| Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty
___________________________________________________________|           |
| P            |        Yes           |        Yes         |           |
| NP           |        Yes           |     Yes or No *    |           |
| NP-Complete  |        Yes           |      Unknown       |           |
| NP-Hard      |     Yes or No **     |      Unknown ***   |           |
____________________________________________________________           V

Remarques sur les entrées Yes ou No :

  • * Un problème de NP qui est aussi P peut être résolu en temps P.
  • ** Un problème NP-difficile qui est également NP-complet est vérifiable en temps P.
  • *** Les problèmes NP-complets (qui forment tous un sous-ensemble de NP-difficile) pourraient l'être. Le reste de NP n'est pas dur.

J'ai aussi trouvé ce schéma très utile pour voir comment tous ces types se correspondent (attention à la moitié gauche du diagramme).

Question

Quelles sont les différences entre NP , NP-Complet et NP-Hard ?

Je suis conscient de nombreuses ressources sur tout le web. J'aimerais lire vos explications, et la raison en est qu'elles peuvent être différentes de ce qui existe, ou c'est là-bas et je ne suis pas au courant.




Si je comprends bien, un problème np-hard n'est pas "plus difficile" qu'un problème np-complete . En fait, par définition, tout problème np-complete est:

  1. à NP
  2. np-hard

- Intro. to Algorithms (3ed) de Cormen, Leiserson, Rivest et Stein, pg 1069




Les problèmes NP-complets sont ceux qui sont à la fois NP-Hard et dans la classe de complexité NP. Par conséquent, pour montrer qu'un problème donné est NP-complet, vous devez montrer que le problème est à la fois dans NP et qu'il est NP-difficile.

Les problèmes qui sont dans la classe de complexité NP peuvent être résolus de manière non déterministe en temps polynomial et une solution possible (un certificat) pour un problème dans NP peut être vérifiée pour l'exactitude en temps polynomial.

Un exemple d'une solution non-déterministe au problème k-clique serait quelque chose comme:

1) sélectionner de manière aléatoire k nœuds à partir d'un graphique

2) vérifier que ces k nœuds forment une clique.

La stratégie ci-dessus est polynomiale dans la taille du graphe d'entrée et donc le problème k-clique est dans NP.

Notez que tous les problèmes résolubles de manière déterministe en temps polynomial sont également en NP.

Montrer qu'un problème est NP-dur implique généralement une réduction d'un autre problème NP-difficile à votre problème en utilisant un mappage temporel polynomial: http://en.wikipedia.org/wiki/Reduction_(complexity)




En plus des autres bonnes réponses, voici le schéma typique que les gens utilisent pour montrer la différence entre NP, NP-Complet et NP-Hard:




P (temps polynomial): Comme son nom le suggère, ce sont les problèmes qui peuvent être résolus en temps polynomial.

NP (temps non-déterministe-polynomial): Ce sont les problèmes de décision qui peuvent être vérifiés en temps polynomial. Cela signifie que si je prétends qu'il existe une solution de temps polynomiale pour un problème particulier, vous me demandez de le prouver. Ensuite, je vais vous donner une preuve que vous pouvez facilement vérifier en temps polynomial. Ces types de problèmes sont appelés problèmes NP. Notez que, ici, nous ne parlons pas de savoir s'il existe une solution de temps polynomiale pour ce problème ou non. Mais nous parlons de vérifier la solution à un problème donné en temps polynomial.

NP-Hard: Ceux-ci sont au moins aussi durs que les problèmes les plus difficiles de NP. Si nous pouvons résoudre ces problèmes en temps polynomial, nous pouvons résoudre n'importe quel problème NP qui peut éventuellement exister. Notez que ces problèmes ne sont pas nécessairement des problèmes NP. Cela signifie que nous pouvons / ne pouvons pas vérifier la solution à ces problèmes en temps polynomial.

NP-Complete: Ce sont les problèmes qui sont à la fois NP et NP-Hard. Cela signifie que si nous pouvons résoudre ces problèmes, nous pouvons résoudre n'importe quel autre problème NP et les solutions à ces problèmes peuvent être vérifiées en temps polynomial.




Related