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



Answers

Qu'est-ce que NP ?

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

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 . Puisqu'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 qui est dans NP est aussi dans NP-complet si et seulement si tous les autres problèmes de NP peuvent être rapidement transformés en x (c'est-à-dire en temps polynomial).

En d'autres termes:

  1. x est dans NP, et
  2. Chaque problème dans NP est reducible à x

Donc, ce qui rend NP-Complete si intéressant est que si l'un des problèmes NP-Complete devait être résolu rapidement, alors tous les problèmes NP peuvent être résolus rapidement.

Voir aussi le post Qu'est-ce que "P = NP?", Et pourquoi est-ce une question aussi célèbre?

Qu'est-ce que NP-Hard ?

NP-Hard sont des problèmes qui sont au moins aussi difficiles que les problèmes les plus difficiles de NP. Notez que les problèmes NP-complets sont également NP-difficile. Cependant, tous les problèmes NP-difficiles ne sont pas NP (ou même un problème de décision), bien qu'ils aient NP comme préfixe. C'est le NP dans NP-dur ne signifie pas le temps polynomial non-déterministe . Oui, c'est confus, mais son utilisation est ancrée et peu susceptible de changer.

Question

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




Il y a une très bonne conférence d'arsdigita sur les mathématiques discrètes qui explique ce qu'est un problème NP-complet.

Les 50 premières minutes sont principalement sur l'algèbre booléenne. Alors sautez directement au début de la minute 53 si vous êtes seulement intéressé par les concepts de P, NP, NP-complétude, le problème de la satisfiabilité booléenne et la réduction.




J'ai entendu une explication, à savoir: "NP-Completeness est probablement l'une des idées les plus énigmatiques dans l'étude des algorithmes." NP "signifie" temps polynomial non déterministe ", et est le nom de ce qu'on appelle une classe de complexité à La chose importante à propos de la classe de complexité NP est que les problèmes de cette classe peuvent être vérifiés par un algorithme de temps polynomial.Par exemple, considérons le problème du comptage de choses Supposons qu'il y ait un tas de pommes sur une table. Le problème est: "Combien de pommes y a-t-il?" 8. Vous pouvez vérifier cette réponse en temps polynomial en utilisant l'algorithme de, duh, en comptant les pommes, en comptant les pommes dans O (n) (c'est la notation Big-oh), car il faut compter une étape 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é comme NP-complet s'il peut être démontré qu'il est à la fois NP-Dur et vérifiable en temps polynomial. Sans aller trop loin dans la discussion de NP-Hard, il suffit de dire qu'il y a certains problèmes auxquels les solutions de temps polynomiales n'ont pas été trouvées. Autrement dit, il faut quelque chose comme n! (n factoriel) étapes pour les résoudre. Cependant, si vous obtenez une solution à un problème NP-Complete, vous pouvez le vérifier en temps polynomial.

Un exemple classique d'un problème NP-complet est le problème du voyageur de commerce. "

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 temps.
  3. Phase de devinette non déterministe && Stade de vérification non déterministe.

Type de problème Np

  1. NP complet
  2. NP dur

NP Problème complet: -

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

  1. Il appartient à la classe NP.
  2. Tout autre problème dans NP peut être transformé en P en temps polynomial.

Quelques Ex: -

  • Problème de sac à dos
  • problème de somme sous-ensemble
  • Vertex couvrant le problème



Si vous cherchez un exemple d'un problème NP-complet, je vous suggère de regarder 3-SAT .

La prémisse de base est que vous avez une expression en forme normale conjonctive , ce qui est une façon de dire que vous avez une série d'expressions jointes par des OR qui doivent toutes être vraies:

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

Le problème 3-SAT est de trouver une solution qui satisfera l'expression où chacune des expressions OR a exactement 3 booléens à faire correspondre:

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

Une solution à celui-ci pourrait être (a = T, b = T, c = F, d = F). Cependant, aucun algorithme n'a été découvert qui résoudra ce problème dans le cas général en temps polynomial. Ce que cela signifie est que la meilleure façon de résoudre ce problème est de faire essentiellement une force brute de deviner et de vérifier et d'essayer différentes combinaisons jusqu'à ce que vous en trouviez une qui marche.

Ce qui est spécial au sujet du problème 3-SAT est que n'importe quel 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 $1,000,000 , sans compter le respect et l'admiration des informaticiens et des mathématiciens du monde entier.




Honnêtement, Wikipedia pourrait être le meilleur endroit pour chercher une réponse à cela.

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




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

1) Problème insoluble 2) Problème intraitable 3) Problème NP 4) Problème P

1) Le premier n'est pas une solution au problème. 2) La seconde est le temps exponentiel du besoin (c'est-à-dire O (2 ^ n) ci-dessus). 3) Le troisième s'appelle le NP. 4) Le quatrième est un problème facile.

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

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

NP Complete: fait référence à Polynomial Time, il nous reste encore à trouver une solution, mais elle peut être vérifiée en temps polynomial. Le problème NPC dans NP est le problème le plus difficile, donc si nous pouvons prouver que nous avons une solution P au problème NPC, alors les problèmes NP qui peuvent être trouvés dans la solution P.

NP Hard: se réfère à Polynomial Time est encore à trouver une solution, mais il n'est certainement pas en mesure de vérifier en temps polynomial. Le problème NP Hard dépasse la difficulté du PNJ.




Related