Ce qui est un problème NP-complet en informatique?
Ce qui est un problème NP-complet de problème? Pourquoi est-il un sujet si important dans l'informatique?
- Vous pouvez être intéressé par les réponses à cette question: stackoverflow.com/questions/111307/...
- J'espère que les gens voir votre commentaire Dan. Depuis NP-complet a beaucoup todo avec P=NP. Peut-être qu'il faut une réponse, ce qui est la norme pour la liaison à des questions connexes dans les environs?
- Eh bien j'ai décidé d'écrire ma propre réponse, car je n'ai pas aimé la façon dont l'on a accepté la réponse est présentée, et inclus un lien vers le P=NP question.
- Il y a un très bon arsdigita conférence sur les mathématiques discrètes qui explique ce qu'est un problème NP-complet de problème. Les 50 premières minutes sont principalement sur l'algèbre booléenne. Alors sautez à droite pour le début de la minute 53 si vous êtes uniquement intéressé par les concepts de P, NP, NP-complétude, de la satisfiabilité booléenne problème et de la réduction.
- Nous ne le saurons jamais, car avec un grand n, il ne sera jamais complète 😉
- Je l'aime et vraiment vous recommandons de vérifier cette explication en vidéo: youtube.com/watch?v=YX40hbAHx3s
Vous devez vous connecter pour publier un commentaire.
NP signifie Non-déterministe Polynôme temps.
Cela signifie que le problème peut être résolu en temps Polynomial Non-déterministe de la machine de Turing (une machine de Turing, mais aussi un non-déterministe "choix" de la fonction). Fondamentalement, une solution doit être tests dans le poly de temps. Si c'est le cas, connus et d'un NP problème peut être résolu en utilisant le problème avec entrée modifiés (un problème NP peut être moins pour le problème donné), alors le problème est NP complet.
La principale chose à prendre à l'écart d'une NP-complets problème est qu'il ne peut pas être résolu en temps polynomial dans tout moyen connu. NP-Dur/NP-Complet est un moyen de montrer que certaines classes de problèmes ne sont pas résoluble en temps réaliste.
Edit: Comme d'autres l'ont mentionné, il y a souvent de l'approximation des solutions de NP-Complet problèmes. Dans ce cas, l'approximation de la solution d'habitude, donne une approximation liée à l'aide de la notation qui nous dit comment fermer le rapprochement est.
Qu'est-ce que NP?
NP est l'ensemble de tous les des problèmes de décision (questions par oui-ou-non-réponse) pour qui le " oui " -les réponses peuvent être vérifié en temps polynomial O(nk) où n est la taille du problème, et k est une constante) par un machine de Turing déterministe. Temps Polynomial est parfois utilisé comme la définition de rapide ou rapidement.
Qu'est-ce que P?
P est l'ensemble de tous les problèmes de décision qui peuvent être résolu dans temps polynomial par un machine de Turing déterministe. Étant donné qu'ils peuvent être résolus en temps polynomial, ils peuvent également être vérifiée en temps polynomial. Donc P est un sous-ensemble de NP.
Qu'est-ce que NP-Complet?
Un problème x qui est dans NP est aussi NP-Complet si et seulement si à tous les problèmes de NP peut être rapidement (c'est à dire. en temps polynomial) qui se transforme en x.
En d'autres termes:
Donc, ce qui rend NP-Complet si intéressant, c'est que si quelqu'un de la NP-Complet problèmes à résoudre rapidement, puis tous les NP problèmes peuvent être résolus rapidement.
Voir aussi le post Ce qui est "P=NP?", et pourquoi est-ce une célèbre question?
Qu'est-ce que NP-Dur?
NP-Dur sont des problèmes qui sont au moins aussi difficile que le plus difficile des problèmes dans NP. Notez que NP-Complet aussi des problèmes NP-dur. Cependant, tous les NP-dur problèmes sont NP (ou même un problème de décision), en dépit d'avoir
NPcomme un préfixe. C'est le NP NP-dur ne signifie pas non-déterministe polynomial en temps. Oui, c'est déroutant, mais son utilisation est bien enclenchée et que peu de chances de changer.NP-Complet signifie quelque chose de très spécifique et vous devez être prudent, ou vous obtiendrez la définition de mal. Tout d'abord, un problème NP est un oui/non problème tel que
Un problème X est NP-Complet si
Si X est NP-complet et un déterministe polynomial en temps de l'algorithme existe peut résoudre toutes les instances de X correctement (0% de faux-positifs, 0% de faux négatifs), alors aucun problème dans NP peut être résolu en déterministes polynomiaux en temps (par la réduction de X).
Jusqu'à présent, personne n'est venu avec une telle déterministe polynomial en temps de l'algorithme, mais personne n'a prouvé l'un n'existe pas (il y a un million de dollars pour toute personne qui peut faire les deux: l'est de la P = NP problème). Cela ne signifie pas que vous ne pouvez pas résoudre une instance particulière d'un NP-Complet (ou NP-Dur) problème. Il signifie simplement que vous ne pouvez pas avoir quelque chose qui va fonctionner de manière fiable sur toutes les instances d'un problème de la même manière que vous pourriez fiable de trier une liste d'entiers. Vous pourriez très bien être en mesure de venir avec un algorithme qui fonctionne très bien sur toutes les instances d'un problème NP-Difficile.
NP-Complet est une classe de problèmes.
La classe
Pse compose de ces problèmes qui sont solubles dans temps polynomial. Par exemple, il pourrait être résolu en temps O(nk) pour une constante k, où n est la taille de l'entrée. Tout simplement, vous pouvez écrire un programme qui sera exécuté dans raisonnable temps.La classe
NPse compose de ces problèmes qui sont vérifiables en temps polynomial. C'est, si on nous donne une solution potentielle, puis nous avons pu vérifier si la solution est correcte en temps polynomial.Quelques exemples sont la Satisfiabilité Booléenne (ou SAT) problème, ou de l'Hamiltonien du cycle de problème. Il ya beaucoup de problèmes qui sont connus pour être dans la classe NP.
NP-Completesignifie que le problème est au moins aussi dur que n'importe quel problème dans NP.Il est important de l'informatique car il a été prouvé que tout problème de NP peut être transformé dans un autre problème NP-complet. Cela signifie qu'une solution à un problème NP-complet de problème est une solution à tous les problèmes NP.
De nombreux algorithmes dans la sécurité repose sur le fait qu'aucun de connu, il existe des solutions pour les problèmes NP-difficile. Il aurait certainement un impact significatif sur le calcul si une solution a été trouvé.
Fondamentalement de ce monde, les problèmes peuvent être classés comme
1) un Problème Insoluble
2) Problème Insoluble
3) NP-Problème
4) P-Problème
1)Le premier est pas une solution au problème.
2)La deuxième est le besoin de temps exponentiel (c'est-à O (2 ^ n) ci-dessus).
3)La troisième est appelée la NP.
4)La quatrième est un problème facile.
P: fait référence à une solution du problème de Temps Polynomial.
NP: renvoie le Polynôme de Temps encore pour trouver une solution. Nous ne sommes pas sûr il n'y a pas de Temps Polynomial une solution, mais une fois que vous fournir une solution, cette solution peut être vérifiée en Temps Polynomial.
NP Complet: désigne en Temps Polynomial nous avons encore à trouver une solution, mais elle peut être vérifiée en Temps Polynomial . Le problème PNJ dans NP est le problème plus difficile à résoudre, si nous pouvons prouver que nous avons P solution à un PNJ problème NP problèmes qui peuvent se trouver dans la P la solution.
NP-Difficile: se réfère Temps Polynomial est encore à trouver une solution, mais il est sûr de ne pas pouvoir être vérifiée en Temps Polynomial . NP-Difficile problème dépasse PNJ difficulté.
C'est une classe de problèmes où l'on doit simuler toutes les possibilités pour être sûr, nous avons la solution optimale.
Il y a beaucoup de bonnes heuristiques pour certains NP-Complet problèmes, mais ils ne sont qu'une supposition, au mieux.
Si vous êtes à la recherche pour un exemple d'un problème NP-complet de problème, alors je vous suggère de prendre un coup d'oeil à 3-SAT.
Le principe de base est que vous avez une expression dans conjonctif forme normale, ce qui est une façon de dire que vous avez une série d'expressions rejoint par Sro que tous doivent être remplies:
Le 3-SAT, le problème est de trouver une solution qui va satisfaire l'expression où chaque de la OU des expressions a exactement 3 booléens de match:
Une solution à cela, on pourrait être (a=T b=T, c=F d=F). Cependant, aucun algorithme n'a été découvert qui permettra de résoudre ce problème dans le cas général en temps polynomial. Ce que cela signifie, c'est que la meilleure façon de résoudre ce problème est essentiellement une force brute deviner et vérifier et essayer les différentes combinaisons jusqu'à ce que vous trouviez celui qui fonctionne.
Ce qui est spécial au sujet de la 3-SAT problème est que TOUTE NP-complets problème peut être réduit à un 3-SAT problème. Cela signifie que si vous pouvez trouver un polynôme en temps de l'algorithme pour résoudre ce problème, puis vous obtenez De 1 000 000 $, pour ne pas mentionner le respect et l'admiration des informaticiens et des mathématiciens du monde entier.
Honnêtement, Wikipédia pourrait être le meilleur endroit pour chercher une réponse à cette question.
Si NP = P, alors on peut résoudre très dur de les problèmes beaucoup plus rapidement que nous avons pensé que nous pourrions avant. Si nous avons à résoudre un seul problème NP-Complet de problème dans P (polynôme) de temps, alors il peut être appliqué à tous les autres problèmes NP-Complets de la catégorie.
Nous devons faire la part des algorithmes et des problèmes. Nous écrire des algorithmes pour résoudre des problèmes, et à plus grande échelle, d'une certaine façon. Bien que ce est une simplification, laissez l'étiquette d'un algorithme avec un " P " si la mise à l'échelle est assez bon, et le 'NP' si elle ne l'est pas.
Il est utile de savoir des choses sur les problèmes que nous essayons de résoudre, plutôt que les algorithmes que nous utilisons pour les résoudre. Donc, nous allons dire que tous les problèmes qui ont une mise à l'échelle de l'algorithme sont des "P". Et ceux qui ont une mauvaise mise à l'échelle de l'algorithme sont "NP".
Qui signifie que beaucoup de problèmes simples sont "NP" trop, parce que nous pouvons écrire un mauvais algorithmes pour résoudre des problèmes simples. Il serait bon de savoir qui des problèmes dans NP sont vraiment difficiles, mais nous ne voulons pas seulement dire "c'est ceux que nous n'avons pas trouvé un bon algorithme pour". Après tout, je pourrais venir avec un problème (l'appeler X) qui, je pense, besoin d'un super-incroyable algorithme. Je dis à tout le monde que le meilleur algorithme que je pouvais venir à résoudre X échelles de mal, et je pense donc que X est un problème plus difficile. Mais demain, peut-être que quelqu'un de plus malin que moi invente un algorithme qui résout X et est dans P. Si ce n'est pas une très bonne définition des problèmes difficiles.
Tout de même, il y a beaucoup de problèmes dans NP que personne ne sait, un bon algorithme pour. Donc, si je pouvais prouver que X est un certain type de problème: celui où un bon algorithme pour résoudre X pourrait aussi être utilisé, dans certains rond-point de la voie, de donner un bon algorithme pour chaque autre problème dans NP. Eh bien maintenant, les gens pourraient être un peu plus convaincu que X est un véritable problème épineux. Et dans ce cas, nous appelons X NP-Complet.
Les définitions pour les NP complet des problèmes ci-dessus est correcte, mais j'ai pensé que je pourrais vanter leur importance philosophique que personne n'a abordé cette question encore.
Presque tous les problèmes complexes bute sera NP Complet. Il y a quelque chose de très fondamental sur cette classe, et qui semble juste pour être en termes de calcul différente de facilement les problèmes solubles. En quelque sorte ils ont leur propre saveur, et il n'est pas difficile de les reconnaître. Cela signifie essentiellement que modérément complexes algorithme est impossible pour vous de résoudre exactement -- planification, l'optimisation, l'emballage, couvrant etc.
Mais tout n'est pas perdu si un problème que vous allez rencontrer est NP Complet. Il y a un vaste domaine très technique où les gens de l'étude de rapprochement des algorithmes, qui vous donnera des garanties pour être proche de la solution de NP problème complet. Certains de ces services sont incroyablement fortes garanties, par exemple, pour 3sat, vous pouvez obtenir un 7/8 garantir, à travers un vraiment évident de l'algorithme. Mieux encore, dans la réalité, il y a quelques très forte heuristiques, qui excellent à donner de grandes réponses (mais pas de garantie!) pour ces problèmes.
Noter que deux très célèbres problèmes -- graph isomorphisme et l'affacturage -- ne sont pas connus pour être P ou NP.
J'ai entendu une explication, qui est:"
NP-Complétude est probablement l'un des plus énigmatique des idées dans l'étude des algorithmes. "NP" signifie "non déterministe polynomial en temps," et est le nom de ce qui est appelé une classe de complexité à laquelle tous les problèmes peuvent appartenir. La chose importante à propos de la NP classe de complexité est que les problèmes à l'intérieur de cette classe peut être vérifié par un algorithme polynomial en temps.
Comme exemple, considérons le problème de comptage des trucs. Supposons qu'il y a un tas de pommes sur une table. Le problème, c'est "Combien de pommes?" Vous sont fournis avec une réponse possible, 8. Vous pouvez vérifier cette réponse en temps polynomial en utilisant l'algorithme d', duh, en comptant les pommes. En comptant les pommes qui se passe en O(n) (c'est Grand-oh notation), parce qu'elle fait un pas de compter chaque pomme. Pour n des pommes, vous avez besoin de n étapes. Ce problème est dans la classe de complexité NP.
Un problème est classée comme NP-complet s'il peut être démontré qu'il est à la fois NP-Dur et vérifiables en temps polynomial. Sans entrer trop profondément dans la discussion d'un problème NP-Difficile, il suffit de dire qu'il existe certains problèmes auxquels temps polynomial solutions n'ont pas été retrouvés. Qui est, il faut quelque chose comme n! (factorielle n) des mesures pour les résoudre. Toutefois, si vous êtes donné une solution à un problème NP-Complet de problème, vous pouvez le vérifier en temps polynomial.
Un exemple classique d'un problème NP-Complet de problème, c'est Le Problème du voyageur de commerce."
De l'auteur: ApoxyButt
De: http://www.everything2.com/title/NP-complete
NP Problème :-
Type de Problème Np
NP Complet de problème :-
1 Problème de Décision A est appelée NP complète si elle a deux propriétés suivantes:-
Certains Ex :-
NP-complet problèmes sont un ensemble de problèmes, à chacune desquelles tout
d'autres NP-problème peut être réduit en temps polynomial, et dont la solution
peut encore être vérifiée en temps polynomial. C'est, de toute NP problème peut être
transformé en l'un de la NP-complet problèmes.
De façon informelle, un NP-complets problème est un problème NP qui est au moins aussi "dur"
comme tout autre problème dans NP.
un NP problème est celui où un algorithme informatique qui vérifie une solution en temps polynomial.
un NP-Complets problème est NP, mais aussi si vous pouvez le résoudre en temps polynomial (P), alors tous les problèmes sont NP P.
Donc get crackin'.