Ce qui est un problème NP-complet ?

Question

Ce qui est un problème NP-complet ? Pourquoi est-ce un tel sujet important en informatique ?

Answer 1

Qu'est-ce que NP?

NP est l'ensemble de tous les problèmes de décision (question avec oui-ou-non-réponse) pour qui le " oui " -les réponses 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. 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ésolus en temps polynomial par une machine de Turing déterministe. Puisque l'on peut résoudre en temps polynomial, il peut aussi être vérifiée en temps polynomial. Donc P est un sous-ensemble de NP.

Ce qui est 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:

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

Donc, ce qui rend NP-Complet si intéressant, c'est que si quelqu'un de la NP-Complet problèmes à résoudre rapidement tous les problèmes NP peut être résolu rapidement. Voir aussi Ce qui est "P=NP?", et pourquoi est-ce une célèbre question?

Ce qui est 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 'NP' comme un préfixe. C'est le NP NP-dur ne signifie pas "non-déterministe polynomial en temps'. Oui c'est confus, mais son utilisation est bien enclenchée et que peu de chances de changer.

Answer 2

NP est synonyme de Non-déterministe Polynomial en 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 testable 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 (NP problème peut être réduit à un 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 raconte comment à proximité de l'approximation.

Answer 3

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

1. Il est polynomiale en temps la preuve pour chaque instance du problème avec une réponse "oui" que la réponse est "oui", ou de manière équivalente)
2. Il existe un polynôme en temps de l'algorithme (éventuellement à l'aide de variables aléatoires) qui a une probabilité non nulle de répondre "oui" si la réponse à une instance du problème est "oui" et dire "non" à 100% du temps si la réponse est "non". En d'autres termes, l'algorithme doit avoir un taux de faux négatifs moins de 100% et pas de faux positifs.

Un problème X est NP-Complet si

1. X est dans NP, et
2. Pour tout problème, Y en NP, il y a une "réduction" de Y à X: un polynôme en temps de l'algorithme qui transforme n'importe quelle instance de Y dans une instance de X telle que la réponse à l'axe de l'instance est "oui" si et seulement si la réponse X-instance est "oui".

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.

Answer 4

En gros, cela les problèmes du monde 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 les PNJ de la difficulté.

Answer 5

Si vous êtes à la recherche pour un exemple d'un problème NP-complet de problème, alors je vous suggère de jeter un oeil à 3-SAT.

Le principe de base est que vous avez une expression en forme normale conjonctive, qui est une façon de dire que vous avez une série d'expressions rejoint par Sro que tous doivent être remplies:

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

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:

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

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, alors vous obtenez de 1 000 000$, pour ne pas mentionner le respect et l'admiration des informaticiens et des mathématiciens du monde entier.