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


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.


906
2017-12-07 01:11


origine


Réponses:


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 un Oui ou non répondre.

Maintenant, laissez-nous définir les classes de complexité.

P

P est une classe de complexité qui représente l'ensemble de tous les problèmes de décision pouvant ê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 graphique connecté G, est-ce que ses sommets peuvent être colorés en utilisant deux couleurs afin 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é témoin) à la réponse étant oui, nous pouvons vérifier qu'il est correct en temps polynomial.

Exemple

Factorisation d'entiers est en NP. C'est le problème que les entiers donnés n et m, y a-t-il un nombre 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 (ils nous remettent des entiers) n et m) et un nombre entier f avec 1 < f < m, et prétendre que f est un facteur de n (le certificat), nous pouvons vérifier la réponse 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 lequel il est possible de réduire tout autre problème NP 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 de temps polynomial f pour transformer des instances y de Y aux 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) c'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 à partir d'une liste prédé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é 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 difficile que les problèmes NP-complets. Notez que les problèmes NP-difficiles ne pas être à NP, et ils ne doivent pas être des problèmes de décision.

La définition précise ici est que 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 donne un programme P et 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 de 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 une solution au problème (Stephen Cook's écriture sur le site Clay est assez 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 contre NP.

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


1178
2017-12-07 01:46



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 n'importe quel NP-Complete 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 P (par exemple, en prouvant P = NP, si vous trouvez comment résoudre un problème NP-Complet dans P heure).

____________________________________________________________
| Type de problème | Vérifiable en P temps | Solvable dans P temps | Difficulté croissante
___________________________________________________________ | |
| P | Oui | Oui | |
| NP | Oui | Oui ou Non * | |
| NP-Complet | Oui | Inconnu | |
| NP-Hard | Oui ou Non ** | Inconnu *** | |
____________________________________________________________ V

Notes sur Yes ou No entrées:

  • * 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 diagramme assez utile pour voir comment tous ces types se correspondent (attention à la moitié gauche du diagramme).


204
2017-10-22 06:08



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 at-il un moyen de marcher un chemin autour de tous les Sept ponts de Königsberg sans prendre deux fois le pont? 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).

UNE problème de décision est une collection de questions avec des réponses oui ou non qui ne varient que dans un paramètre. Dites le problème COMPOSITE = {"Est n composite": n est un entier} ou EULERPATH = {"Est-ce que le graphique G avoir 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 attendre 2002 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 chaque problème de décision qui se prête à des preuves efficaces a une solution efficace? Personne ne 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 chaque autre problème NP. Une solution efficace pour le problème de satisfiability booléen pourrait être utilisé 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 quelque sorte les problèmes les plus «difficiles» de NP, sont connus sous le nom de NP-complet problèmes.

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 peuvent 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 est appelé NP-difficile.


70
2017-12-07 02:42



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

enter image description here


49
2017-11-24 17:50



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" 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».


40
2017-08-08 20:41



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.


34
2017-10-04 03:50



Je pense que nous pouvons y répondre beaucoup plus succinctement. J'ai répondu à un question connexeet copiant 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.


16
2018-06-18 16:52



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 (c'est-à-dire, 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)


15
2017-12-07 01:45



Il y a de très bonnes réponses pour cette question particulière, donc il n'y a pas de raison d'écrire ma propre explication. Je vais donc essayer de contribuer avec une excellente ressource sur les 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 à propos de différents problèmes de complexité de calcul. Mis à part les problèmes posés par OP, il énumérait environ 500 classes différentes de problèmes de calcul avec de belles descriptions et aussi la liste des documents de recherche fondamentale qui décrivent la classe.


5
2018-01-14 01:56



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

  1. à NP
  2. np-hard

enter image description here

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


2
2017-08-13 13:57