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





problème problèmes (10)


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.

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




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

Mais d'abord, un problème NP-difficile est un problème pour lequel nous ne pouvons pas prouver qu'il existe une solution de temps polynomiale. La dureté NP de certains "problèmes-P" est généralement prouvée en convertissant un problème NP-difficile 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-difficile appartient à l'ensemble NP, alors il est NP-complet. Pour appartenir à l'ensemble NP, un problème doit être

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

Maintenant, il est facile de voir qu'il pourrait y avoir beaucoup de problèmes NP-difficiles qui n'appartiennent pas à NP et qui sont plus difficiles à résoudre. Comme exemple intuitif, la version d'optimisation du vendeur itinérant où nous devons trouver un calendrier réel est plus difficile que la version de décision du vendeur itinérant où nous devons juste déterminer si un programme avec une longueur <= k existe ou non.




Je vais faire ça simple,

P - Problèmes qui peuvent être résolus en temps polynomial.

NP - Problèmes qui peuvent être vérifiés en temps polynomial.

Par conséquent, tout problème P est également un NP car tout problème P peut également être vérifié en temps polynomial, mais viceversa n'est pas vrai car tout problème NP ne peut pas être résolu en temps polynomial.

Maintenant, voici nos problèmes représentés en utilisant un diagramme de Venn >>,

NP Hard: Si tous les problèmes de NP sont réductibles à un problème encore plus difficile, alors ce problème est appelé NP difficile.

Voici le diagramme de Venn >>,

NP Complete: Si un problème NP est à l'intérieur de l'ensemble des problèmes NP, alors NP est terminé,

J'espère que cela vous donne la clarté.

Merci d'avoir lu.




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:




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).




C'est une réponse très informelle à la question posée.

Est-ce que 3233 peut être écrit comme le produit de deux autres nombres plus grands que 1? Y a-t-il un moyen de contourner les Sept Ponts de Königsberg sans prendre de pont deux fois? Ce sont des exemples de questions qui partagent un trait commun. Il n'est peut-être pas évident de déterminer la réponse de manière efficace, mais si la réponse est «oui», alors il y a une vérification rapide et rapide. Dans le premier cas, une factorisation non triviale de 51; dans la seconde, un itinéraire pour la marche des ponts (adapté aux 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 = {"Is n composite": n est un entier} ou EULERPATH = {"Est-ce que le graphe G a un chemin d'Euler?": G est un graphe fini}.

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

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 un élément d'information supplémentaire, il est évident que vous devez 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 de 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, la simple division longue est un moyen efficace de voir qu'ils sont corrects.

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

La recherche d'algorithmes se poursuit et de nouveaux algorithmes intelligents sont créés tout le temps. Un problème que vous ne savez peut-être pas résoudre efficacement aujourd'hui peut s'avérer être une solution efficace (sinon évidente) demain. En fait, il a fallu aux chercheurs jusqu'en 2002 pour trouver une solution efficace à COMPOSITE! Avec toutes ces avancées, il faut vraiment se demander: est-ce que ce 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 venu avec la découverte d'une classe particulière de problèmes NP. En jouant avec des modèles de circuit pour le calcul, Stephen Cook a trouvé un problème de décision de la variété NP qui était prouvé aussi dur ou plus difficile que tous les autres problèmes NP. Une solution efficace pour le problème de la satisfiabilité booléenne pourrait être utilisée pour créer une solution efficace à tout autre problème dans NP. Peu 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 «difficiles» du NP, sont devenus des problèmes NP-complets .

Bien sûr, NP est seulement 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 variables qui rendent vraie l'expression booléenne suivante". Bien que l'on puisse dire de façon informelle que certains de ces problèmes sont «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 (sans décision) conduirait directement à une solution efficace à tout problème NP. Un problème comme celui-ci s'appelle NP-hard .




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, souvenons-nous d'un concept préliminaire nécessaire pour comprendre ces définitions.

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

Maintenant, laissez-nous définir 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é un exemple du problème, la réponse par oui ou par non peut être décidée en temps polynomial.

Exemple

Étant donné un graphe connexe G , ses sommets peuvent-ils être colorés en utilisant deux couleurs de sorte qu'aucun bord 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 n'avez plus de sommets ou que vous êtes obligé de créer un bord et que ses deux extrémités ont 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é un témoin) à la réponse étant oui, nous pouvons vérifier qu'il est correct en temps polynomial.

Exemple

La factorisation en nombre entier est en NP. C'est le problème que les entiers n et m donnés, y a-t-il un entier f avec 1 < f < m , tel que f divise n ( f est un petit facteur de n )?

C'est un problème de décision parce que les réponses sont oui ou non. Si quelqu'un nous donne une instance du problème (donc ils nous donnent des entiers n et m ) et un entier f avec 1 < f < m , et prétendent que f est un facteur de n (le certificat), nous pouvons vérifier la réponse dans temps polynomial en effectuant la division n / f .

NP-Complet

NP-Complete est une classe de complexité qui représente l'ensemble de tous les problèmes X dans NP pour lesquels il est possible de réduire tout autre problème NP de Y à X en temps polynomial.

Intuitivement cela signifie que nous pouvons résoudre Y rapidement si nous savons comment résoudre X rapidement. Précisément, Y est réductible à X , s'il existe un algorithme polynomial f pour transformer les instances y de Y en instances x = f(y) de X en temps polynomial, avec la propriété que la réponse à y est 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 (ANDs) de disjonctions à 3 clauses (ORs), 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ù chaque 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 de 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 peut être résolu en temps polynomial (un problème pour tous les gouverner).

NP-difficile

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 X est NP-difficile, s'il y a un problème NP-complet Y , tel que Y est réductible à X en temps polynomial .

Mais comme n'importe quel problème NP-complet peut être réduit à n'importe quel autre problème NP-complet en temps polynomial, tous les problèmes NP-complets peuvent être réduits à n'importe quel problème NP-difficile en temps polynomial. Ensuite, s'il y a une solution à un problème NP-difficile 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 que, étant donné un programme P et une entrée I , s'arrêtera-t-il? 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 célèbre en informatique, et l'une des questions les plus importantes en suspens dans les sciences mathématiques. En fait, le Clay Institute offre un million de dollars pour résoudre le problème (l'article de Stephen Cook sur le site Web de Clay est plutôt bon).

Il est clair que P est un sous-ensemble de NP. La question ouverte est de savoir si les problèmes NP ont des solutions de temps polynomiales déterministes. On croit en grande partie qu'ils ne le font pas. Voici un article récent remarquable sur la dernière (et l'importance) du problème P = NP: Le statut du problème P versus NP .

Le meilleur livre sur le sujet est Ordinateurs et Intractability par Garey et Johnson.




La façon 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 de choix multiples».

Lorsque vous essayez de résoudre un "problème de mot", 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 un «problème de mots», soit essayer de brancher chacune des réponses qui vous sont données et choisir la réponse qui vous convient.

Il arrive souvent qu'un "problème à choix multiples" soit beaucoup plus facile que le "problème par mot" correspondant: substituer les réponses candidates et vérifier qu'elles s'adaptent peut nécessiter beaucoup moins d'efforts que de trouver la bonne réponse à partir de zéro.

Maintenant, si nous acceptons l'effort qui prend le temps polynomial "facile" alors la classe P consisterait en "problèmes de mots faciles", et la classe NP serait constituée de "problèmes faciles à choix multiple".

L'essence de P v. NP est la question: "Y a-t-il des problèmes faciles à choix multiples qui ne sont pas faciles comme 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 rien est difficile?

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

Enfin, les problèmes NP-complets sont ceux qui sont simultanément NP et NP-difficile. Suivant notre analogie, ils sont à la fois «faciles comme problèmes de choix multiples» et «le plus dur de tous comme problèmes de mots».




Au lieu de l'expliquer avec des mots, voici un exemple. Ceci est une version Scheme de la fonction factorielle:

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

Voici une version de factorielle qui est récursive à la queue:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

Vous remarquerez dans la première version que l'appel récursif aux faits est introduit dans l'expression de multiplication, et que l'état doit donc être sauvegardé sur la pile lors de l'appel récursif. Dans la version récursive en queue, aucune autre expression S n'attend la valeur de l'appel récursif et comme il n'y a pas d'autre travail à faire, l'état n'a pas besoin d'être sauvegardé sur la pile. En règle générale, les fonctions de récurrence de queue Scheme utilisent un espace de pile constant.





algorithm complexity-theory computer-science np-complete np-hard