Qu'est-ce qu'un NP-complet en informatique?

StackOverflow https://stackoverflow.com/questions/210829

Question

Qu'est-ce qu'un problème NP-complet? Pourquoi est-ce un sujet aussi important en informatique?

Était-ce utile?

La solution

NP signifie un polynôme non déterministe .

Cela signifie que le problème peut être résolu en temps polynomial en utilisant une machine de Turing non déterministe (similaire à une machine de Turing classique, mais incluant également une fonction "choix" non déterministe). Fondamentalement, une solution doit être testable en temps universel. Si tel est le cas et si un problème connu de NP peut être résolu en utilisant le problème donné avec une entrée modifiée (un problème de NP peut être réduit au problème donné), le problème est NP complet.

Le problème essentiel à résoudre pour résoudre un problème NP-complet est qu’il ne peut être résolu de manière connue en temps polynomial. NP-Hard / NP-Complete est un moyen de montrer que certaines catégories de problèmes ne peuvent pas être résolues dans des délais réalistes.

Modifier: comme d’autres l’ont déjà noté, il existe souvent des solutions d’approximation pour les problèmes NP-Complete. Dans ce cas, la solution d'approximation donne généralement une approximation liée en utilisant une notation spéciale qui indique la proximité de l'approximation.

Autres conseils

Qu'est-ce que NP ?

NP est l'ensemble de tous les problèmes de décision (questions avec réponse oui ou non). ) pour lesquels les réponses positives peuvent être vérifiées en temps polynomial (O (n k ) où n est la taille du problème, et k est une constante) par une machine de Turing déterministe . Le temps polynomial est parfois utilisé comme définition de rapide ou rapidement .

Qu'est-ce que P ?

P est l’ensemble des problèmes de décision qui peuvent être résolus en temps polynomial par une machine de Turing déterministe . Comme ils peuvent être résolus en temps polynomial, ils peuvent également être vérifiés en temps polynomial. Donc, P est un sous-ensemble de NP.

Qu'est-ce que NP-Complete ?

Un problème x dans NP est également dans NP-Complete si et seulement si tous les autres problèmes dans NP peuvent être rapidement transformés (c'est-à-dire en temps polynomial) en x.

En d'autres termes:

  1. x est dans NP et
  2. Chaque problème dans NP est réductible à x

Ce qui rend NP-Complete aussi intéressant, c’est que si l’un des problèmes NP-Complete devait être résolu rapidement, tous les problèmes NP peuvent être résolus rapidement.

Voir aussi le message Qu'est-ce que "P = NP? & Quot ;, et pourquoi est-ce une question aussi célèbre?

Qu'est-ce que NP-Hard ?

NP-Hard sont des problèmes au moins aussi difficiles que les problèmes les plus difficiles de NP. Notez que les problèmes NP-Complete sont aussi NP-difficiles. Cependant, tous les problèmes NP-difficiles ne sont pas NP (ni même un problème de décision), malgré le préfixe NP . C’est-à-dire que NP dans NP-difficile ne signifie pas temps polynomial non déterministe . Oui, c'est déroutant, mais son utilisation est enracinée et il est peu probable qu'elle change.

NP-Complete signifie quelque chose de très spécifique et vous devez faire attention, sinon vous aurez une mauvaise définition. Premièrement, un problème NP est un problème oui / non tel que

  1. Il existe une preuve polynomiale pour chaque instance du problème avec un "oui". répondez que la réponse est "oui", ou (de manière équivalente)
  2. Il existe un algorithme à temps polynomial (utilisant éventuellement des variables aléatoires) qui a une probabilité non nulle de répondre "oui". si la réponse à une instance du problème est " yes " et dira "non" 100% du temps si la réponse est "non". En d’autres termes, l’algorithme doit avoir un taux de faux négatifs inférieur à 100% et ne pas comporter de faux positifs.

Un problème X est NP-complet si

  1. X est dans NP et
  2. Pour tout problème Y dans NP, il existe une "réduction". de Y à X: algorithme polynomial qui transforme n'importe quelle instance de Y en une instance de X telle que la réponse à l'instance Y soit "oui". si et seulement si l'instance X de réponse est "oui".

Si X est NP-complet et qu'il existe un algorithme déterministe à temps polynomial capable de résoudre toutes les instances de X correctement (0% de faux positifs, 0% de faux négatifs), alors tout problème de NP peut être résolu de manière déterministe. -polynomial-time (par réduction à X).

Jusqu’à présent, personne n’avait imaginé un tel algorithme déterministe, mais personne n’avait prouvé qu’il en existait un (il ya un million de dollars pour quiconque peut le faire non plus: il s’agit du P = problème NP}). Cela ne signifie pas que vous ne pouvez pas résoudre un cas particulier de problème NP-Complete (ou NP-Hard). Cela signifie simplement que vous ne pouvez pas obtenir quelque chose qui fonctionne de manière fiable sur toutes les instances d'un problème de la même manière que vous pouvez trier de manière fiable une liste d'entiers. Vous pourriez très bien être en mesure de concevoir un algorithme qui fonctionnera très bien avec toutes les instances pratiques d’un problème NP-Hard.

NP-Complete est une classe de problèmes.

La classe P comprend les problèmes pouvant être résolus dans le temps polynomial . Par exemple, elles pourraient être résolues en O (n k ) pour une constante k, où n est la taille de l'entrée. Autrement dit, vous pouvez écrire un programme qui fonctionnera dans un temps raisonnable .

La classe NP comprend les problèmes vérifiables en temps polynomial. Autrement dit, si on nous donne une solution potentielle, nous pourrons alors vérifier si la solution donnée est correcte en temps polynomial.

Quelques exemples sont le problème de la satiabilité booléenne (ou SAT ) ou le problème du cycle hamiltonien. Il existe de nombreux problèmes connus dans la classe NP.

NP-Complete signifie que le problème est au moins aussi difficile que tout problème dans NP.

Il est important pour l’informatique car il a été prouvé que tout problème dans NP peut être transformé en un autre problème dans NP-complete. Cela signifie qu'une solution à tout problème de NP-complet est une solution à tous les problèmes de NP.

De nombreux algorithmes de sécurité dépendent du fait qu’aucune solution connue n’existe pour les problèmes difficiles de NP. Si une solution était trouvée, cela aurait sans aucun doute un impact significatif sur l'informatique.

En gros, les problèmes de ce monde peuvent être classés comme

& nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 1) problème insoluble & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 2) Problème Intractable & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 3) NP-problème & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 4) Problème P

& nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 1) Le premier n’est pas une solution au problème. & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 2) Le second est le temps exponentiel nécessaire (c’est-à-dire O (2 ^ n) ci-dessus). & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 3) Le troisième s'appelle le NP. & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; 4) Le quatrième problème est facile.

P: se réfère à une solution du problème du temps polynomial.

NP: fait référence au temps polynomial pour trouver une solution. Nous ne sommes pas sûrs qu’il n’existe pas de solution de temps polynomial, mais une fois que vous avez fourni une solution, cette solution peut être vérifiée en temps polynomial.

NP Complete: pour l'heure polynomiale, il nous reste encore à trouver une solution, mais elle peut être vérifiée en temps polynomial Le problème des PNJ dans les PN est le problème le plus difficile. Par conséquent, si nous pouvons prouver que nous avons une solution P au problème des CNP, les problèmes NP peuvent être résolus dans la solution P.

NP Difficile: référence Le temps polynomial n’a pas encore trouvé de solution, mais il n’est certainement pas possible de le vérifier dans le temps polynomial. Le problème difficile de NP dépasse la difficulté des PNJ.

Il s’agit d’une classe de problèmes dans laquelle nous devons simuler toutes les possibilités pour pouvoir disposer de la solution optimale.

Il existe de nombreuses heuristiques intéressantes pour certains problèmes NP-Complete, mais ce n’est au mieux qu’une supposition éclairée.

Si vous recherchez un exemple de problème NP-complet, je vous suggère de consulter 3-SAM .

Le principe de base est que vous avez une expression dans la forme normale conjonctive , ce qui permet de: dire que vous avez une série d'expressions jointes par des blocs opératoires qui doivent tous être vrais: 

(a or b) and (b or !c) and (d or !e or f) ...

Le problème des 3-SAT consiste à trouver une solution qui satisfasse l'expression dans laquelle chacune des expressions OR a exactement 3 booléens à rechercher: 

(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...

Une solution à celle-ci pourrait être (a = T, b = T, c = F, d = F). Cependant, aucun algorithme n'a été découvert pour résoudre ce problème dans le cas général en temps polynomial. Cela signifie que le meilleur moyen de résoudre ce problème consiste à effectuer essentiellement des tests de force brute et à essayer différentes combinaisons jusqu'à ce que vous en trouviez une qui fonctionne.

La particularité du problème 3-SAT est que TOUT problème NP-complet peut être réduit à un problème 3-SAT. Cela signifie que si vous pouvez trouver un algorithme polynomial pour résoudre ce problème, vous obtenez alors 1 000 000 $ , sans oublier le respect et l'admiration des informaticiens et des mathématiciens du monde entier.

Honnêtement, Wikipedia pourrait être le meilleur endroit pour trouver une réponse à cette question.

Si NP = P, nous pouvons résoudre des problèmes très difficiles beaucoup plus rapidement que nous ne le pensions auparavant. Si nous résolvons un seul problème NP-Complete en temps P (polynomial), il peut être appliqué à tous les autres problèmes de la catégorie NP-Complete.

Nous devons séparer les algorithmes et les problèmes. Nous écrivons des algorithmes pour résoudre des problèmes, et ils s’échelonnent d’une certaine manière. Bien que ce soit une simplification, étiquetons un algorithme avec un "P" si la mise à l'échelle est suffisante, et "NP" si ce n'est pas le cas.

Il est utile de connaître les problèmes que nous essayons de résoudre, plutôt que les algorithmes que nous utilisons pour les résoudre. Donc, nous dirons que tous les problèmes qui ont un algorithme de bonne mise à l'échelle sont "dans P". Et ceux qui ont un algorithme d'échelle médiocre sont "en NP".

Cela signifie que de nombreux problèmes simples se posent "dans NP". aussi, parce que nous pouvons écrire de mauvais algorithmes pour résoudre des problèmes faciles. Il serait bon de savoir quels problèmes dans NP sont vraiment complexes, mais nous ne voulons pas simplement dire "ce sont ceux pour lesquels nous n'avons pas trouvé de bon algorithme". Après tout, je pourrais trouver un problème (appelez-le X) qui, à mon avis, nécessite un algorithme extraordinaire. Je dis au monde que le meilleur algorithme que je pourrais trouver pour résoudre mal l'échelle X, et donc je pense que X est un problème vraiment difficile. Mais demain, peut-être que quelqu'un de plus intelligent que moi inventera un algorithme qui résout X et qui est en P. Donc, ce n'est pas une très bonne définition des problèmes difficiles.

Néanmoins, il y a beaucoup de problèmes dans NP pour lesquels personne ne connaît un bon algorithme. Donc, si je pouvais prouver que X est un certain type de problème: celui dans lequel un bon algorithme pour résoudre X pourrait également être utilisé, de façon détournée, pour donner un bon résultat. algorithme pour tous les autres problèmes de NP. Eh bien, les gens sont peut-être un peu plus convaincus que X est un problème réellement délicat. Et dans ce cas, nous appelons X NP-Complete.

Les définitions des problèmes complets NP ci-dessus sont correctes, mais j’ai pensé que je pourrais me laisser aller à des paroles sur leur importance philosophique car personne n’a encore abordé cette question.

Presque tous les problèmes complexes que vous rencontrerez seront NP Complete. Il y a quelque chose de très fondamental dans cette classe, et qui semble simplement être différent des problèmes facilement résolvables. Ils ont en quelque sorte leur propre goût et il n’est pas si difficile de les reconnaître. Cela signifie qu’il est impossible pour un algorithme moyennement complexe de résoudre exactement - ordonnancement, optimisation, emballage, etc.

Mais tout n’est pas perdu si le problème que vous rencontrez est NP Complete. Il existe un vaste domaine très technique où les gens étudient des algorithmes d’approximation, ce qui vous donnera des garanties d’être proches de la solution d’un problème complet de NP. Certaines d'entre elles sont des garanties incroyablement fortes - par exemple, pour 3sat, vous pouvez obtenir une garantie 7/8 par le biais d'un algorithme vraiment évident. Mieux encore, en réalité, il existe des heuristiques très puissantes, qui excellent à donner de bonnes réponses (mais aucune garantie!) À ces problèmes.

Notez que deux problèmes très connus - l’isomorphisme des graphes et la factorisation - ne sont pas connus pour être P ou NP.

J'ai entendu une explication, à savoir: " La NP-Completeness est probablement l'une des idées les plus énigmatiques de l'étude des algorithmes. "NP" signifie "temps polynomial non déterministe", et est le nom de ce qu'on appelle une classe de complexité à laquelle les problèmes peuvent appartenir. L'important dans la classe de complexité NP est que les problèmes de cette classe peuvent être vérifiés par un algorithme polynomial. A titre d'exemple, considérons le problème du comptage de choses. Supposons qu'il y a un tas de pommes sur une table. Le problème est "Combien y at-il de pommes?" Une réponse possible vous est fournie, 8. Vous pouvez vérifier cette réponse en temps polynomial en utilisant l’algorithme de, duh, compter les pommes. Le comptage des pommes se fait en temps O (n) (c'est la notation Big-oh), car il faut un pas pour compter chaque pomme. Pour n pommes, vous avez besoin de n étapes. Ce problème est dans la classe de complexité NP.

Un problème est classé dans la catégorie NP-complet s'il est possible de prouver qu'il est à la fois NP-Difficile et vérifiable en temps polynomial. Sans entrer trop dans le débat sur NP-Hard, il suffit de dire qu'il existe certains problèmes pour lesquels aucune solution temporelle polynomiale n'a été trouvée. C'est-à-dire qu'il faut quelque chose comme n! (n factoriel) étapes pour les résoudre. Toutefois, si vous avez une solution à un problème NP-Complete, vous pouvez le vérifier en temps polynomial.

Le problème du voyageur de commerce est un exemple classique de problème NP-Complete. "

L'auteur: ApoxyButt De: http://www.everything2.com/title/NP-complete

Problème NP: -

  1. Le problème NP est un problème qui peut être résolu en temps polynomial non déterministe.
  2. L'algorithme non déterministe fonctionne en deux étapes.
  3. Phase de détermination non déterministe & amp; & amp; Étape de vérification non déterministe.

Type de problème Np

  1. NP complète
  2. NP dur

Problème NP Complete: -

1 Décision Le problème A est appelé NP complet s'il possède les deux propriétés suivantes: -

  1. Il appartient à la classe NP.
  2. Tous les autres problèmes de NP peuvent être transformés en P en temps polynomial.

Certains Ex: -

  • Problème de sac à dos
  • problème de somme d'ensemble
  • Problème couvrant le sommet

Les problèmes NP-complets sont un ensemble de problèmes pour chacun desquels autre problème NP peut être réduit en temps polynomial, et dont la solution peut encore être vérifié en temps polynomial. Autrement dit, tout problème de NP peut être transformé en l'un des problèmes NP-complet. - De manière informelle, un problème NP-complet est un problème NP qui est au moins aussi "difficile". comme tout autre problème dans NP.

Un problème NP est un problème où un algorithme informatique vérifiant une solution peut être créé en temps polynomial.

Un problème NP-complet est NP, mais si vous pouvez le résoudre en temps polynomial (appelé P), tous les problèmes NP sont P.

Alors faites-vous craquer.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top