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

Je connais de nombreuses ressources sur le Web. J'aimerais lire vos explications, et la raison en est qu'elles peuvent être différentes de ce qui existe, ou qu'il y a quelque chose que je ne connais pas.

Je suppose que vous recherchez des définitions intuitives, car les définitions techniques nécessitent un certain temps pour être comprises. Tout d'abord, rappelons-nous un concept préliminaire nécessaire pour comprendre ces définitions.

• Problème de décision : Un problème avec une réponse oui ou non .

Maintenant, définissons ces classes de complexité .

P

P est une classe de complexité qui représente l'ensemble de tous les problèmes de décision qui peuvent être résolus en temps polynomial .

Autrement dit, étant donné une instance du problème, la réponse oui ou non peut être décidée en temps polynomial.

Exemple

Étant donné un graphe connecté G, ses sommets peuvent-ils être colorés à l'aide de deux couleurs afin qu'aucune arête ne soit monochromatique?

Algorithme: commencez par un sommet arbitraire, colorez-le en rouge et tous ses voisins en bleu et continuez. Arrêtez-vous lorsque vous manquez de sommets ou que vous êtes obligé de créer une arête dont les deux extrémités sont de la même couleur.

NP

NP est une classe de complexité qui représente l'ensemble de tous les problèmes de décision pour lesquels les instances où la réponse est «oui» ont des preuves qui peuvent être vérifiées en temps polynomial.

Cela signifie que si quelqu'un nous donne une instance du problème et un certificat (parfois appelé témoin) pour que la réponse soit oui, nous pouvons vérifier qu'il est correct en temps polynomial.

Exemple

La factorisation entière est en NP. C'est le problème que, étant donné les nombres entiers netm , y a-t-il un entier favec 1 < f < m, qui fdivise n( fest un petit facteur de n)?

Il s'agit d'un problème de décision car les réponses sont oui ou non. Si quelqu'un nous remet une instance du problème (alors il nous remet des entiers net m) et un entier favec1 < f < m , et prétendent que fc'est un facteur de n(le certificat), nous pouvons vérifier la réponse en temps polynomial en effectuant la division n / f.

NP-Complete

NP-complet est une classe de complexité qui représente l'ensemble de tous les problèmes Xde NP pour lesquels il est possible de réduire tout autre problème NP Yà Xtemps polynomiale.

Intuitivement, cela signifie que nous pouvons résoudre Yrapidement si nous savons comment résoudre Xrapidement. Précisément, Yest réductible à X, s'il existe un algorithme polynomial de temps fpour transformer des instances yde Yen instancesx = f(y) de Xtemps polynomial, avec la propriété que la réponse à yest oui, si et seulement si la réponse àf(y) est oui.

Exemple

3-SAT. C'est le problème dans lequel on nous donne une conjonction (ET) de disjonctions à 3 clauses (OU), des déclarations de la forme

(x_v11 OR x_v21 OR x_v31) AND 
(x_v12 OR x_v22 OR x_v32) AND 
...                       AND 
(x_v1n OR x_v2n OR x_v3n)

où chacun x_vij est une variable booléenne ou la négation d'une variable d'une liste prédéfinie finie (x_1, x_2, ... x_n).

On peut montrer que chaque problème NP peut être réduit à 3-SAT . La preuve en est technique et nécessite l'utilisation de la définition technique de NP ( basée sur des machines de Turing non déterministes ). Ceci est connu comme le théorème de Cook .

Ce qui rend les problèmes NP-complets importants, c'est que si un algorithme de temps polynomial déterministe peut être trouvé pour résoudre l'un d'entre eux, chaque problème NP est résoluble en temps polynomial (un problème pour les gouverner tous).

NP-dur

Intuitivement, ce sont les problèmes qui sont au moins aussi difficiles que les problèmes NP-complets . Notez que les problèmes NP-difficiles ne doivent pas être dans NP , et ils ne doivent pas être des problèmes de décision .

La définition précise ici est qu'un problème Xest NP-difficile, s'il y a un problème NP-complet Y, tel qu'il Yest réductible Xen temps polynomial .

Mais comme tout problème NP-complet peut être réduit à tout autre problème NP-complet en temps polynomial, tous les problèmes NP-complet peuvent être réduits à tout problème NP-dur en temps polynomial. Ensuite, s'il existe une solution à un problème NP-dur en temps polynomial, il y a une solution à tous les problèmes NP en temps polynomial.

Exemple

Le problème d'arrêt est un problème NP-difficile. C'est le problème qui, compte tenu d'un programme Pet d'une entrée I, va-t-il s'arrêter? C'est un problème de décision mais ce n'est pas dans NP. Il est clair que tout problème NP-complet peut être réduit à celui-ci. Comme autre exemple, tout problème NP-complet est NP-difficile.

Mon problème NP-complet préféré est le problème du démineur .

P = NP

Celui-ci est le problème le plus connu en informatique et l'une des questions en suspens les plus importantes en sciences mathématiques. En fait, le Clay Institute offre un million de dollars pour une solution au problème (la publication de Stephen Cook sur le site Web de Clay est assez bonne).

Il est clair que P est un sous-ensemble de NP. La question ouverte est de savoir si les problèmes NP ont ou non des solutions temporelles polynomiales déterministes. On pense généralement que non. Voici un article récent exceptionnel sur le dernier (et l'importance) du problème P = NP: Le statut du problème P versus NP .

Le meilleur livre sur le sujet est Computers and Intractability de Garey et Johnson.

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-Complete , et tout NP-Complete peut être réduit à NP-Hard , le tout en P (polynôme).

Si vous pouvez résoudre une classe de problèmes 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 savez comment résoudre tout problème NP-Complete dans Temps P).

____________________________________________________________
| Type de problème | Vérifiable en temps P | Solvable en temps P | Augmentation de la difficulté
___________________________________________________________ | |
| P | Oui | Oui | |
| NP | Oui | Oui ou non * | |
| NP-Complete | Oui | Inconnu | |
| NP-Hard | Oui ou non ** | Inconnu *** | |
____________________________________________________________ V

Notes sur YesouNo entrées:

• * Un problème NP qui est également P est résoluble en temps P.
• ** Un problème NP-Hard qui est également NP-Complete est vérifiable en temps P.
• *** Les problèmes NP-Complete (qui forment tous un sous-ensemble de NP-hard) peuvent être. Le reste de NP n'est pas dur.

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

Il s'agit d'une réponse très informelle à la question posée.

3233 peut-il être écrit comme le produit de deux autres nombres supérieurs à 1? Y a-t-il un moyen de parcourir un chemin autour de tous les sept ponts de Königsberg sans prendre deux fois un pont? Ce sont des exemples de questions qui partagent un trait commun. Il n'est peut-être pas évident de savoir comment déterminer efficacement la réponse, mais si la réponse est «oui», il existe une preuve de vérification courte et rapide. Dans le premier cas, une factorisation non triviale de 51; dans le second, un itinéraire pour parcourir les ponts (en respectant les contraintes).

Un problème de décision est un ensemble de questions avec des réponses oui ou non qui ne varient que dans un paramètre. Dites le problème COMPOSITE = {"Est ncomposite": nest un entier} ou EULERPATH = {"Le graphe Ga- t- il un chemin d'Euler?": GEst un graphe fini}.

Maintenant, certains problèmes de décision se prêtent à des algorithmes efficaces, sinon évidents. Il y a plus de 250 ans, Euler a découvert un algorithme efficace pour des problèmes tels que les "Sept ponts de Königsberg".

D'un autre côté, pour de nombreux problèmes de décision, il n'est pas évident de savoir comment obtenir la réponse - mais si vous connaissez des informations supplémentaires, il est évident comment prouver que vous avez la bonne réponse. COMPOSITE est comme ceci: la division d'essai est l'algorithme évident, et c'est lent: pour factoriser un nombre à 10 chiffres, vous devez essayer quelque chose comme 100 000 diviseurs possibles. Mais si, par exemple, quelqu'un vous a dit que 61 est un diviseur de 3233, une simple division longue est un moyen efficace de voir si elles sont correctes.

La classe de complexité NP est la classe de problèmes de décision où les réponses «oui» ont des preuves courtes à énoncer, rapides à vérifier. Comme COMPOSITE. Un point important est que cette définition ne dit rien sur la gravité du problème. Si vous avez un moyen correct et efficace de résoudre un problème de décision, il suffit de noter les étapes de la solution.

La recherche sur les algorithmes se poursuit et de nouveaux algorithmes intelligents sont constamment créés. Un problème que vous ne savez peut-être pas comment résoudre efficacement aujourd'hui peut s'avérer avoir une solution efficace (sinon évidente) demain. En fait, il a fallu des chercheurs jusqu'en 2002 pour trouver une solution efficace à COMPOSITE! Avec toutes ces avancées, il faut vraiment se demander: est-ce que le fait d'avoir des preuves courtes n'est qu'une illusion? Peut-être que chaque problème de décision qui se prête à des preuves efficaces a une solution efficace? Personne ne le sait .

Peut-être la plus grande contribution à ce domaine est venue avec la découverte d'une classe particulière de problèmes de NP. En jouant avec des modèles de circuits pour le calcul, Stephen Cook a trouvé un problème de décision de la variété NP qui était manifestement aussi difficile ou plus difficile que tout autre problème NP. Une solution efficace pour le problème de satisfiabilité booléenne pourrait être utilisée pour créer une solution efficace à tout autre problème dans NP. Peu de temps après, Richard Karp a montré qu'un certain nombre d'autres problèmes de décision pouvaient servir le même objectif. Ces problèmes, en un sens les problèmes les plus "durs" de NP, sont devenus connus sous le nom de problèmes NP-complets .

Bien sûr, NP n'est qu'une classe de problèmes de décision. De nombreux problèmes ne sont pas naturellement énoncés de cette manière: "trouver les facteurs de N", "trouver le chemin le plus court dans le graphe G qui visite chaque sommet", "donner un ensemble d'affectations de variables qui rend l'expression booléenne suivante vraie". Bien que l'on puisse parler de manière informelle que certains de ces problèmes sont "dans NP", techniquement cela n'a pas beaucoup de sens - ce ne sont pas des problèmes de décision. Certains de ces problèmes pourraient même avoir le même type de puissance qu'un problème NP-complet: une solution efficace à ces problèmes (non décisionnels) conduirait directement à une solution efficace à tout problème NP. Un problème comme celui-ci est appelé NP-hard .

P (Temps polynomial): Comme son nom l'indique, ce sont les problèmes qui peuvent être résolus en temps polynomial.

NP (Temps polynomial non déterministe): 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 temporelle polynomiale pour un problème particulier, vous me demandez de le prouver. Ensuite, je vous donnerai une preuve que vous pourrez 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 l'existence d'une solution temporelle polynomiale pour ce problème ou non. Mais nous parlons de vérifier la solution à un problème donné en temps polynomial.

NP-Hard: Ce sont au moins aussi difficiles que les problèmes les plus difficiles de NP. Si nous pouvons résoudre ces problèmes en temps polynomial, nous pouvons résoudre tout 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 tout autre problème NP et les solutions à ces problèmes peuvent être vérifiées en temps polynomial.

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

La manière la plus simple d'expliquer P v. NP et autres sans entrer dans les détails techniques est de comparer les "problèmes de mots" avec les "problèmes à choix multiples".

Lorsque vous essayez de résoudre un «problème de mots», vous devez trouver la solution à partir de zéro. Lorsque vous essayez de résoudre un "problème à choix multiples", vous avez le choix: soit le résoudre comme vous le feriez pour un "problème de mots", soit essayez de brancher chacune des réponses qui vous sont données et choisissez la réponse candidate qui vous convient.

Il arrive souvent qu'un «problème à choix multiple» soit beaucoup plus facile que le «problème de mots» correspondant: remplacer les réponses des candidats et vérifier si elles correspondent peut nécessiter beaucoup moins d'efforts que de trouver la bonne réponse à partir de zéro.

Maintenant, si nous convenions que l'effort qui prend un temps polynomial est "facile", alors la classe P serait constituée de "problèmes de mots faciles", et la classe NP serait constituée de "problèmes de choix multiples faciles".

L'essence de P c. NP est la question: "Existe-t-il des problèmes de choix multiples faciles qui ne sont pas faciles comme des problèmes de mots"? Autrement dit, y a-t-il des problèmes pour lesquels il est facile de vérifier la validité d'une réponse donnée, mais trouver cette réponse à partir de zéro est difficile?

Maintenant que nous comprenons intuitivement ce qu'est le NP, nous devons contester notre intuition. Il s'avère qu'il y a des "problèmes à choix multiples" qui, dans un certain sens, sont les plus difficiles de tous: si l'on pouvait trouver une solution à l'un de ces problèmes "les plus difficiles de tous", on pourrait trouver une solution à TOUS Problèmes NP! Lorsque Cook l'a découvert il y a 40 ans, cela a été une surprise totale. Ces problèmes «les plus difficiles d'entre eux» sont connus sous le nom de NP-hard. Si vous trouvez une "solution de problème de mots" à l'un d'eux, vous trouverez automatiquement une "solution de problème de mots" à chaque "problème de choix multiple facile"!

Enfin, les problèmes NP-complets sont ceux qui sont simultanément NP et NP-durs. Selon notre analogie, ils sont à la fois "faciles comme des problèmes à choix multiples" et "les plus difficiles d'entre eux comme des problèmes de mots".

Les problèmes NP-complets sont ceux qui sont à la fois NP-durs 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 (c'est-à-dire un certificat) pour un problème en NP peut être vérifiée pour l'exactitude en temps polynomial.

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

1) sélectionner au hasard k nœuds dans 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 de la k-clique est dans NP.

Notez que tous les problèmes résolus 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-dur à votre problème en utilisant un mappage temporel polynomial: http://en.wikipedia.org/wiki/Reduction_(complexity)

Je pense que nous pouvons y répondre de manière beaucoup plus succincte. J'ai répondu à une question connexe et copié ma réponse à partir de là

Mais d'abord, un problème NP-dur est un problème pour lequel nous ne pouvons pas prouver qu'une solution temporelle polynomiale existe. La dureté NP de certains "problème-P" est généralement prouvée en convertissant un problème NP-dur déjà éprouvé en "problème-P" en temps polynomial.

Pour répondre au reste de la question, vous devez d'abord comprendre quels problèmes NP-difficiles sont également NP-complets. Si un problème NP-hard appartient à set NP, il est NP-complete. Pour appartenir à NP set, un problème doit être

(i) un problème de décision,
(ii) le nombre de solutions au problème doit être fini et chaque solution doit être de longueur polynomiale, et
(iii) étant donné une solution de longueur polynomiale, nous devrions être en mesure de dire si la réponse à la le problème est oui / non

Maintenant, il est facile de voir qu'il pourrait y avoir de nombreux problèmes NP-difficiles qui n'appartiennent pas à NP défini et sont plus difficiles à résoudre. À titre d'exemple intuitif, la version d'optimisation de voyageur de commerce où nous devons trouver un horaire réel est plus difficile que la version de décision de voyageur de commerce où nous avons juste besoin de déterminer si un horaire de longueur <= k existe ou non.

Il y a vraiment de bonnes réponses à cette question particulière, il est donc inutile d'écrire ma propre explication. Je vais donc essayer de contribuer avec une excellente ressource sur différentes classes de complexité de calcul.

Pour quelqu'un qui pense que la complexité de calcul ne concerne que P et NP, voici la ressource la plus exhaustive sur les différents problèmes de complexité de calcul. Outre les problèmes posés par OP, il a répertorié environ 500 classes différentes de problèmes de calcul avec de belles descriptions et également la liste des documents de recherche fondamentale qui décrivent la classe.

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-complet est:

1. en NP
2. np-hard

- Intro. aux algorithmes (3ed) par Cormen, Leiserson, Rivest et Stein, p. 1069

Trouvez une définition intéressante: