Quelles sont les différences entre NP, NP-complet et NP-dur?

https://stackoverflow.com/questions/1857244

13-09-2019
|

Question

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

Je suis au courant de beaucoup de ressources sur tout le web. Je voudrais lire vos explications, et la raison en est qu'ils pourraient être différents de ce qui est là-bas, ou il y a quelque chose que je ne suis pas au courant.

La solution

Je suppose que vous êtes à la recherche de définitions intuitives, étant donné que les définitions techniques nécessitent un certain temps pour comprendre. Tout d'abord, rappelons un concept préliminaire nécessaire pour comprendre ces définitions.

problème de décision : Un problème avec un oui ou pas Réponse

Maintenant, définissons les 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 .

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

Exemple

Etant donné un G de graphe connexe, ses sommets peuvent être colorés en utilisant deux couleurs de sorte qu'aucun bord est monochromatique?

Algorithme: commencer par un sommet arbitraire, la couleur rouge et il tous ses voisins bleu et continuer. Arrêtez-vous lorsque vous manquez de sommets ou vous êtes obligé de faire un bord ont tous les deux de ses extrémités 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 cas 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 un exemple du problème et un certificat (parfois appelé un témoin) à la réponse étant oui, nous pouvons vérifier qu'il est correct dans le temps polynomiale.

Exemple

Entier factorisation est dans NP. Tel est le problème que les entiers donnés n et m, est-il un f entier avec 1 < f < m, de telle sorte que f divise n (f est un petit facteur de n)?

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

NP-complet

NP-complet 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 Y à X en temps polynomial.

Intuitivement, cela signifie que nous pouvons résoudre rapidement Y si nous savons comment résoudre X rapidement. Précisément, Y est réductible à X, s'il y a un algorithme polynomial f pour transformer les 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) est oui.

Exemple

3-SAT. C'est le problème où nous donne une conjonction (ANDS) de disjonctions 3 article (ORS), les 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 de (x_1, x_2, ... x_n) finie.

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

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

NP-dur

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

La définition précise est ici que un X problème est NP-dur, s'il y a un problème NP-complet Y, de sorte que Y est réductible à X en temps polynomial .

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

Exemple

problème de l'arrêt est un problème NP-dur. Tel est le problème qui donne un P du programme et l'entrée I, il va arrêter? Ceci est un problème de décision, mais il est pas dans NP. Il est clair que tout problème NP-complet peut être réduit à celui-ci. Autre exemple, un problème NP-complet est NP-dur.

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

P = NP

Celui-ci est le problème le plus célèbre dans l'informatique, et l'une des plus importantes questions en suspens dans les sciences mathématiques. En fait, l'Institut Clay offre un million de dollars pour un solution au problème ( writeup sur le site de 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 polynomial déterministe. Il est en grande partie pense qu'ils ne le font pas. Voici un article récent exceptionnel sur le dernier (et l'importance) du problème P = NP: le statut du problème P par rapport à NP .

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

Autres conseils

Je l'ai regardé autour et de voir beaucoup d'explications longues. Voici un petit graphique qui peut être utile de résumer:

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

Si vous pouvez résoudre une classe plus difficile de problème dans le temps P, cela signifie que vous trouvé comment résoudre tous les problèmes plus facilement dans le temps P (par exemple, prouver P = NP, si vous comprenez comment résoudre tout NP- problème complet dans le temps P).

____________________________________________________________
| 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

Notes sur les entrées de Yes ou No:

* Un problème NP qui est aussi P est résoluble dans le temps P.
** Un problème NP-dur qui est aussi NP-complet est vérifiable dans le temps P.
*** NP-complets problèmes (tous qui forment un sous-ensemble de NP-dur) pourrait être. Le reste du NP est difficile de ne pas.

J'ai aussi trouvé ce diagramme très utile de voir comment tout ces types correspondent les uns aux autres (accorder plus d'attention à la moitié gauche du diagramme).

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

Peut être écrit 3233 comme le produit de deux autres nombres plus grand que 1? Est-il possible de marcher sur un chemin autour de tous les Sept ponts de Königsberg sans prendre un pont deux fois? Ce sont des exemples de questions qui partagent un trait commun. Il peut ne pas être évident de déterminer efficacement la réponse, mais si la réponse est « oui », alors il y a une courte et rapide pour vérifier la preuve. Dans le premier cas une factorisation non triviale de 51; dans le second, un itinéraire pour la marche des ponts (mise en place des contraintes).

problème de décision est une collection de questions par oui ou non des réponses qui varient que dans un seul paramètre. Dire que le problème COMPOSITES = { "Est-composite n": n est un entier} ou {EULERPATH = "Est-ce que G graphique ont un chemin Euler?": G est un graphe fini}.

Maintenant, certains problèmes de décision se prêtent à l'efficacité, sinon des algorithmes é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.

Par contre, pour de nombreux problèmes de décision, il est pas évident comment obtenir la réponse - mais si vous connaissez une information supplémentaire, il est évident comment s'y prouver que vous avez la bonne réponse. COMPOSITES est comme ceci: Section de première instance est l'algorithme évident, et il est lent: de factoriser un numéro à 10 chiffres, vous devez essayer quelque chose comme 100.000 possibles diviseurs. Mais si, par exemple, quelqu'un vous a dit que 61 est un diviseur de 3233, 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 » ont court à l'autre, de vérifier rapidement les preuves. Comme COMPOSITES. Un point important est que cette définition ne dit rien sur la façon dont le problème est difficile. Si vous avez un bon, moyen efficace de résoudre un problème de décision, juste écrire les étapes de la solution est une preuve suffisante.

Les algorithmes de recherche continue et de nouveaux algorithmes intelligents sont créés tout le temps. Un problème que vous pourriez ne pas savoir comment résoudre efficacement aujourd'hui peut se révéler avoir demain une solution efficace (sinon évidente). En fait, il a fallu des chercheurs jusqu'à 2002 pour trouver une solution efficace pour COMPOSITES! Avec tous ces progrès, on a vraiment à se demander: Est-ce peu d'avoir des preuves courtes juste une illusion? Peut-être que tous problème de décision qui se prête à des preuves efficaces a une solution efficace? .

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 constaté un problème de décision de la variété NP qui était démontrable aussi dur ou plus dur que tous autre problème NP. Une solution efficace pour problème sat du pourrait être utilisé pour créer un système efficace solution à tout autre problème NP. Peu après, Richard Karp a montré qu'un certain nombre d'autres problèmes de décision pourrait servir le même but. Ces problèmes, dans un sens, les problèmes les plus difficiles "dans" NP, est devenu connu sous le nom NP-complets problèmes .

Bien sûr, NP est seulement une classe de problèmes de décision. De nombreux problèmes ne sont pas naturellement déclaré de cette manière: « trouver les facteurs de N », « trouver le chemin le plus court dans le graphe G qui visite tous les sommets », « donner un ensemble de missions variables qui rend vraie l'expression booléenne suivante ». Bien que l'on peut de façon informelle talk au sujet de certains de ces problèmes étant « dans NP », sur le plan technique qui ne fait pas beaucoup de sens - ils ne sont pas des problèmes de décision. Certains de ces problèmes pourraient même avoir la même sorte de pouvoir comme un problème NP-complet: une solution efficace à ces (non décision) problèmes conduirait directement à une solution efficace à un problème NP. Un problème comme celui-ci est appelé NP-dur .

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

entrer image description ici

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

NP (temps non déterministe polynomiale): Ce sont les problèmes de décision qui peuvent être vérifiées en temps polynomial. Cela signifie que, si je prétends qu'il ya une solution 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. Ce genre de problèmes sont appelés problèmes NP. Notez que, ici nous ne parlons pas de savoir s'il y a une solution polynomial pour ce problème ou non. Mais nous parlons de la vérification de la solution à un problème donné dans le temps polynomiale.

NP-Hard: Ce sont au moins aussi dur que les problèmes les plus difficiles dans NP. Si nous pouvons résoudre ces problèmes en temps polynomiale, nous pouvons résoudre tous les problèmes NP qui peuvent exister. Notez que ces problèmes ne sont pas nécessairement des problèmes NP. Cela signifie, nous pouvons / peut-pas vérifier la solution à ces problèmes en temps polynomiale.

NP-complet: Ce sont les problèmes qui sont à la fois NP et NP-dur. 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és en temps polynomial.

La meilleure façon d'expliquer P v. NP et ce sans entrer dans technicités est de comparer « les problèmes de mots » avec « plusieurs problèmes de choix ».

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 « plusieurs problèmes de choix », vous avez le choix: soit résoudre comme vous le feriez un « problème de mot », ou essayer de brancher chacun des réponses données à vous, et choisissez la réponse candidat qui convient.

Il arrive souvent qu'un « problème de choix multiple » est beaucoup plus facile que le « problème de mot » correspondant. Remplaçant les réponses de candidats et de 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 accepterions l'effort qui prend du temps polynomiale « facile » alors la classe P consisterait « problèmes de mots faciles », et la classe NP est composé de « facile de multiples problèmes de choix ».

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

Maintenant que nous comprenons intuitivement ce que NP est, nous devons remettre en question notre intuition. Il se trouve qu'il ya des « multiples problèmes de choix » qui, dans un certain sens, sont les plus difficiles de tous: si l'on veut trouver une solution à l'un de ces « plus difficiles de tous » problèmes que l'on serait en mesure de trouver une solution à tous problèmes NP! Lorsque Cook découvrit cela il y a 40 ans, il est venu comme une surprise complète. Ces « plus durs d'entre eux tous les problèmes » sont connus comme NP-dur. Si vous trouvez une « solution de problème de mot » à l'un d'entre eux vous trouveriez automatiquement une « solution de problème de mot » à chaque « problème de choix multiples facile »!

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

Je pense que nous pouvons répondre beaucoup plus succincte. Je répondu à une question relative et copier 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 polynomiale existe. NP-dureté de certains « problème-P » est généralement prouvé par la conversion d'un problème NP-dur déjà fait ses preuves au « 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-complet. Si un problème NP-dur appartient à l'ensemble NP, alors il est NP-complet. Appartenir à mettre 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 doit être d'une 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 ne font pas partie de mettre en NP et sont plus difficiles à résoudre. À titre d'exemple intuitive, la version d'optimisation du voyageur de commerce où nous avons besoin de trouver un calendrier réel est plus difficile que la version de décision du vendeur voyage où nous avons juste besoin de déterminer si un programme de longueur <= k existe ou non.

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

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 (à savoir un certificat) pour un problème NP peut être vérifiée pour l'exactitude en temps polynomial.

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

1) de façon aléatoire de sélection des noeuds de k à partir d'un diagramme

2) vérifier que ces noeuds k forment une clique.

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

Notez que tous les problèmes résolubles en temps déterministe polynomiale sont également NP.

Montrer que 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 de temps polynomial: http://en.wikipedia.org/wiki/Reduction_ (complexité)

Il y a des réponses vraiment sympa pour cette question particulière, donc il n'y a pas de point 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 est seulement P et NP, ici est la ressource la plus exhaustive sur les différents problèmes de complexité de calcul . Outre les problèmes posées par OP, elle a énuméré environ 500 classes de problèmes de calcul avec des descriptions agréables et aussi la liste des documents de recherche fondamentale qui décrivent la classe.

Si je comprends bien, un np dur problème n'est pas "plus difficile" que d'un np-complet problème. En fait, par définition, tous les problèmes np-complet est:

dans NP
np dur

- Intro. à Algorithmes (3ed) par Cormen, Leiserson, Rivest et Stein, 1069 pg

Trouver une défintion intéressante:

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow