Quelles sont les différences entre vs vs NP-complet de NP NP-difficile ?
Je suis conscient des nombreuses ressources partout sur le web. Je voudrais lire vos explications, et la raison est qu’ils soient différents alors ce qui est là-bas, ou il est là-bas et je ne suis pas au courant.
Je suppose que vous êtes à la recherche pour intuitive définitions les définitions techniques sont, ainsi, techniques et requièrent très peu de temps pour comprendre). Commençons par la définition de NP.
Problème de décision: Une question avec une réponse oui ou non.
P: Un problème de décision qui peuvent être résolus en temps polynomial. C'est, compte tenu d'une instance du problème, la réponse est oui ou non peut être décidé en temps polynomial.
Exemple: étant Donné un graphe connecté G, peut de ses sommets être colorée à l'aide de deux couleurs, de sorte qu'aucune arête est monochromatique. Algorithme: commencer par l'arbitraire d'un sommet, de couleur rouge et l'ensemble de ses voisins, de bleu et de continuer. Arrêtez-vous lorsque vous exécutez notre de sommets ou vous êtes forcé de faire un bord ont à la fois de ses extrémités être de la même couleur.
NP: UN problème de décision où les instances du problème, pour lequel la réponse est oui ont les 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'elle est correcte en temps polynomial.
Exemple: factorisation d'Entiers est NP. C'est le problème que, compte tenu des entiers n et m, est-il un entier f avec 1 < f < m tels 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 tend une instance du problème (de sorte qu'ils nous les entiers n et m) et un entier f avec 1 < f < m et prétendent qu' f est un facteur de n (le certificat), nous pouvons vérifier la réponse en temps polynomial en effectuant la division de l' n / f.
NP-complet: Un problème NP X pour lesquels il est possible de réduire tout problème NP Y de X en temps polynomial. Intuitivement, cela signifie que nous ne 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 en temps f pour transformer les instances y de Y de cas x = f(y) de X en temps polynomial avec la propriété que la réponse à la y est oui si et seulement si la réponse à l' f(y) est oui.
Exemple: 3-SAT. C'est le problème dans lequel il nous est donné une conjonction de 3-clause de disjonctions (c'est à dire, 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 durée de liste prédéfinie (x_1, x_2, ... x_n). Il peut être montré que chaque NP problème peut être réduit à 3-SAT. La preuve, c'est technique et nécessite l'utilisation de la technique de définition de NP (basée sur la non-déterministe des machines de Turing). Ceci est connu en tant que Cuisinier du théorème.
Ce qui rend NP-complet problèmes important, c'est que si un déterministe polynomial en temps de l'algorithme permettant de résoudre l'un d'eux, tous les NP problème est résoluble en temps polynomial (un problème pour les gouverner tous).
NP-dur: Intuitivement, ce sont ces problèmes qui sont encore plus difficiles que le NP-complet problèmes. Notez que NP-dur les problèmes n'ont pas à être dans NP (ils n'ont pas à être des problèmes de décision). La définition précise ici, est-ce un problème X est NP-difficile si il y a un problème NP-complet de problème, Y tels que Y est réductible X en temps polynomial. Mais depuis toute NP-complets problème peut être réduit à tout autre NP-complet de problème en temps polynomial, toutes NP-complet problèmes peuvent être réduits à tout problème NP-difficile en temps polynomial. Alors si 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.
Le problème de l'arrêt est le classique problème NP-difficile. C'est le problème que, étant donné un programme P et d'entrée I, il va les arrêter? C'est un problème de décision, mais il n'est pas dans NP. Il est clair que toute NP-complets problème peut être réduit à celui-ci.
P = NP: C'est la plus célèbre problème en informatique, et l'une des plus importantes questions 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 writeup sur le site web de l'Argile est assez bon). Il est clair que P est un sous-ensemble de NP. La question ouverte est de savoir si ou non NP problèmes ont déterministe polynomial en temps des solutions. Il est considéré qu'ils ne le font pas. Voici un remarquable article récent sur le dernier (et l'importance) de la P = NP problème: Le Statut de la P versus NP problème.
Le meilleur livre sur le sujet est d' Ordinateurs et Intraitable par Garey et Johnson. Mon préféré NP-complets problème est le dragueur de mines de problème.
J'ai été en regardant autour et de voir beaucoup de longues explications. Voici un petit tableau qui peut être utile de les résumer. Remarquez comment la difficulté augmente du haut vers le bas: tout le NP peut être réduite à un problème NP-Complet et toute NP-Complet peut être réduite à un problème NP-Difficile, tout en P de temps. Si vous pouvez résoudre les plus difficiles de la classe de problème en P de temps, cela signifiera que vous trouvé la façon de résoudre tous les plus facile des problèmes dans P (par exemple, en prouvant P = NP si vous le trouver comment résoudre tout problème NP-Complet de problème en P de temps).
____________________________________________________________ | Type de problème | Vérifiables P temps | Résoluble en P de temps | Difficulté Croissante ___________________________________________________________| | | P | Oui | Oui | | | NP | Oui | Oui ou Non * | | | NP-Complet | Oui | Non | | | NP-Dur | Oui ou Non * * * | Non | | ____________________________________________________________ V
Notes sur 'Oui ou Non' entrées:
J'ai aussi trouvé ce schéma très utile de voir comment tous ces types correspondent les uns aux autres (payer plus d'attention à la moitié gauche du schéma).
C'est un très informel de répondre à la question posée.
Peut 3233 être écrit comme le produit de deux autres nombres plus grands que 1? Est-il possible de marcher un chemin à travers tous les Sept Ponts de Königsberg , sans prendre le pont à deux reprises? Ces sont des exemples de questions qui partagent un trait commun. Il peut ne pas être évident pour vous de déterminer efficacement la réponse, mais si la réponse est "oui", alors il y a un court et rapide pour vérifier la preuve. Dans le premier cas, un non-trivial de la factorisation de 51; dans le second, un parcours pour la marche de la des ponts (côté les contraintes).
Un problème de décision est une collection de questions avec des réponses oui ou non qui ne varient que par un seul paramètre. Dire que le problème COMPOSITE={"Est - n composite": n est un entier} ou EULERPATH={"signifie le graphique G ont une Euler chemin?": G est finie graphique}.
Maintenant, certains problèmes de décision se prêtent à l'efficace, si pas évident algorithmes. Euler a découvert un algorithme efficace pour des problèmes comme les "Sept Ponts de Königsberg" plus de 250 ans.
D'autre part, pour de nombreux problèmes de décision, il n'est pas évident comment faire pour obtenir la réponse, mais si vous connaissez un élément d'information complémentaire, il est évident comment prouver que vous avez le droit de réponse. COMPOSITE se présente comme suit: section de première instance, constitue à l'évidence de l'algorithme, et c'est lent: décomposer un nombre à 10 chiffres, vous devez essayer quelque chose comme 100 000 diviseurs. Mais si, par exemple, quelqu'un vous 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ù le " oui " des réponses courtes à l'état, rapide pour vérifier les preuves. Comme COMPOSITE. Un point important est que cette définition ne dit rien sur la façon dont dur est le problème. Si vous avez un bon, un moyen efficace de résoudre un problème de décision, tout simplement écrire les étapes de la solution est une preuve suffisante.
Les algorithmes de recherche continue, et de nouveaux algorithmes intelligents qui sont créés tous les jours. Un problème que vous pourriez ne pas savoir comment résoudre efficacement aujourd'hui peut s'avérer efficace (pas si évident), la solution de demain. En fait, il a fallu des chercheurs jusqu'à 2002 pour trouver une solution efficace afin de COMPOSITE! Avec tous ces progrès, on a vraiment à se demander: Est-ce peu sur de courtes épreuves qu'une illusion? Peut-être que chaque problème de décision qui se prête à l'efficacité des preuves a une solution efficace? Personne ne le sait.
Peut-être la plus grande contribution à ce champ de recherche est venu avec la découverte d'un particulier de la classe des problèmes NP. En jouant autour avec des modèles de circuits de calcul, Stephen Cook trouvé un problème de décision de la NP variété qui a été sensiblement aussi difficile ou plus difficile que tous les autres NP problème. Une solution efficace pour la satisfiabilité booléenne problème pourrait être utilisé pour créer une solution efficace pour tout autre problème dans NP. Peu après, Richard Karp a montré qu'un certain nombre d'autres problèmes de décision peut-elle servir le même but. Ces problèmes, en un sens, le "noyau dur" des problèmes dans NP, est devenu connu comme NP-complet problèmes.
Bien sûr, le NP n'est qu'une classe de problèmes de décision. De nombreux problèmes ne sont pas naturellement a déclaré de cette manière: "rechercher les facteurs de N", "trouver le plus court chemin dans le graphe G qui visite tous les sommets", "donner un ensemble d'assignations de variables qui rend le suivant expression booléenne true". Si l'on peut de manière informelle parler de certains de ces problèmes "NP", technique qui n'a pas beaucoup de sens -- ils ne sont pas des problèmes de décision. Certains de ces problèmes pourraient même avoir le même genre de pouvoir que d'une NP-complets problème: une solution efficace à ces (non-décision) problèmes conduisent directement à une solution efficace pour tout problème NP. Un problème comme celui-ci est appelé NP-dur.
La façon la plus simple d'expliquer v. P NP et sans entrer dans les subtilités, est de comparer les "problèmes" avec la "les choix multiples problèmes".
Lorsque vous essayez de résoudre un "problème mot" vous devez trouver la solution à partir de zéro. Lorsque vous essayez de résoudre un "choix multiples problèmes", vous avez le choix: soit à résoudre comme vous le feriez d'un "mot" du problème, ou à essayer de le brancher dans chacune des réponses données pour vous, et de choisir le candidat à la réponse qui convient.
Il arrive souvent qu'un "choix multiple" du problème est beaucoup plus facile que le "mot" du problème: la substitution de la les réponses des candidats et de vérifier s'ils peuvent nécessitent beaucoup moins d'effort que de trouver la bonne réponse à partir de zéro.
Maintenant, si nous sommes d'accord l'effort qui prend un temps polynomial "facile", alors la classe P consisterait à "easy word problèmes", et la classe NP serait composé de "facile à choix multiples problèmes".
L'essence de P v. NP est la question: "Est-il facile à choix multiples problèmes qui ne sont pas facile comme mot de problèmes"? C'est, il y a des problèmes pour lesquels il est facile de vérifier la validité d'une réponse, mais pour trouver la réponse à partir de zéro est difficile?
Maintenant que nous comprenons intuitivement ce que NP est, nous avons pour défi de notre intuition. Il s'avère qu'il y a des "choix multiples problèmes" que, dans un certain sens, sont plus difficile de tous: si l'on veut trouver une solution à l'un de ces "plus dur de tous les" problèmes que l'on serait en mesure de trouver une solution à TOUS les problèmes NP! Lorsque Cook a découvert cela il y a 40 ans, il est venu comme une surprise totale. Ces "plus dur de tous" les problèmes sont connus comme NP-dur. Si vous trouvez un "mot solution du problème" à l'un d'eux vous de trouver automatiquement un "mot solution du problème" à chaque "facile à choix multiple problème"!
Enfin, NP-complet problèmes sont ceux qui sont à la fois NP et NP-dur. Suite à notre analogie, ils sont en même temps faciles à choix multiples problèmes" et "le plus dur de tous comme des problèmes".
Je pense que nous pouvons répondre qu'il est beaucoup plus succinctement. J'ai répondu à une question connexe, et la copie de ma réponse à partir de là
Mais d'abord, un problème NP-difficile est un problème pour lequel on ne peut pas prouver qu'un temps polynomial une solution existe. NP-dureté de certains problème "P" est généralement prouvé par la conversion d'un déjà prouvé problème NP-difficile de le problème "P" en temps polynomial.
Pour répondre au reste de la question, vous devez d'abord comprendre ce qui NP-dur aussi des problèmes NP-complet. Si un problème NP-difficile appartient à l'ensemble de NP, alors qu'il est NP-complet. Pour appartenir à l'ensemble de NP, un problème doit être
(i) un problème de décision,
(ii) le nombre de solutions du problème doit être finie, et chaque solution doit être de polynôme de longueur, et
(iii) étant donné un polynôme de la longueur de la solution, nous devrions être en mesure de dire si la réponse à la question est oui/nonMaintenant, il est facile de voir qu'il y a de nombreux NP-dur de problèmes qui n'appartiennent pas à l'ensemble de NP et sont plus difficiles à résoudre. Comme un exemple intuitif, l'optimisation de la version de voyageur de commerce où nous avons besoin de trouver un calendrier réel est plus difficile que la décision-version du voyageur de commerce, où nous avons juste besoin de déterminer si un calendrier avec une longueur <= k existe ou pas.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
