Qu'est-ce qu'un NP-complet en informatique?
Qu'est-ce qu'un NP-complete problem? Pourquoi est-ce un sujet aussi important en informatique?
2 réponses
NP signifie Non déterministe Polynôme du temps.
cela signifie que le problème peut être résolu en temps Polynomial à l'aide d'une machine de Turing non déterministe (comme une machine de Turing régulière mais incluant également une fonction de" choix " non déterministe). Fondamentalement, une solution doit être testable en poly time. Si c'est le cas, et un problème NP connu peut être résolu en utilisant le problème donné avec l'entrée modifiée (un problème NP peut être réduit au problème donné) alors le problème est NP complet.
la principale chose à retirer d'un NP-problème complet est qu'il ne peut pas être résolu en temps polynomial de n'importe quelle manière connue. NP-Hard / NP-Complete est une façon de montrer que certaines classes de problèmes ne peuvent pas être résolus en temps réel.
Edit: comme d'autres l'ont noté, il y a souvent approximation solutions pour NP-problèmes complets. Dans ce cas, la solution d'approximation donne habituellement une limite d'approximation en utilisant une notation spéciale qui nous dit à quel point l'approximation est proche.
Qu'est-ce que NP ?
NP est l'ensemble de problèmes de décision (questions avec réponse par oui ou non) pour lesquelles les réponses "Oui" peuvent être vérifié en temps polynomial (O(n k ) où n est la taille du problème, et k est une constante) par une machine déterministe de Turing . 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 dans heure polynomiale par une machine déterministe de Turing . Étant donné qu'ils peuvent être résolus en temps polynomial, ils peuvent également être vérifiée dans le polynôme temps. Par conséquent, 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-remplir si et seulement si tous les autres problèmes dans NP peuvent être rapidement (c.-à-d. en temps polynomial) transformé en X.
en d'autres termes:
- x est en NP, et
- chaque problème dans NP est réductible à x
ainsi, 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 Ce qui est "P=NP?"et pourquoi est-ce une célèbre question?