Différence entre un problème NP-Complet et NP-Difficile

NP-Complet et NP-Difficile les deux sont des classes de complexité, ce qui signifie qu’il s’agit de deux ensembles de problèmes de décision (c’est-à-dire des problèmes pour lesquels la réponse est «oui» ou «non»). Est-ce que 2x + 3x − 2 = 0? Un ensemble de nombres a-t-il un sous-ensemble qui correspond à une valeur souhaitée? Un graphe contient-il un circuit eulérien? Ce sont tous des exemples de problèmes de décision.
 
 

 
D’abord, rappelons-nous un concept préliminaire nécessaire pour comprendre ces définitions.

 

Problème P

P est une classe de complexité qui représente l’ensemble des problèmes de décision pouvant être résolus en temps polynomial. Autrement dit, étant donné un exemple du problème, la réponse « oui » ou « non » peut être décidée en temps polynomial.

Puisqu’ils peuvent être résolus en temps polynomial, ils peuvent également être vérifiés en temps polynomial. Par conséquent, P est un sous-ensemble de NP.

Exemple :
Avec un graphe G connecté, peut-on colorer ses sommets en utilisant deux couleurs afin qu’aucun bord ne soit monochromatique?

Algorithme: commencez avec un sommet arbitraire, colorez-le en vert et tous ses voisins en bleu et continuez. Arrêtez-vous lorsque vous êtes à court de sommets ou que vous devez créer une arête pour que ses deux extrémités aient la même couleur.
 

Problème NP

Un problème est attribué à la classe NP (temps polynomial non déterministe) si elle est résolue en temps polynomial par une machine de Turing non déterministe.

Un problème P (dont le temps de résolution est limité par un polynôme) est toujours aussi NP. Si un problème est connu comme étant NP et si une solution au problème est connue, la démonstration de l’exactitude de la solution peut toujours être réduite à une vérification P (temps polynomial). Si P et NP ne sont pas équivalents, la solution des problèmes de NP nécessite (dans le pire des cas) une recherche exhaustive.

La programmation linéaire, connue depuis longtemps comme étant NP et supposée ne pas être P, a été démontrée par L. Khachian en 1979. Il est important de déterminer si tous les problèmes apparemment liés aux NP sont réellement P.
 
 

Problème NP-difficile

Un problème est dit NP-difficile si un algorithme pour le résoudre peut être traduit en un pour résoudre tout autre problème NP. Il est beaucoup plus facile de montrer qu’un problème est NP que de montrer que c’est NP-difficile. Un problème à la fois NP et NP-difficile est appelé un problème NP-complet.
 

Problème NP-complet

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

En d’autres termes:

• x est dans NP, et
• Chaque problème dans NP est réductible à x

Donc, ce qui rend NP-Complete si intéressant, c’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.
 

P = NP

Celui-ci est le problème le plus célèbre en informatique, et l’une des questions en suspens les plus importantes en mathématiques. En fait, Clay Institute offre un million de dollars pour trouver une solution à ce problème.

Il est clair que P est un sous-ensemble de NP. La question ouverte est de savoir si les problèmes de NP ont des solutions déterministes en temps polynomial. On pense généralement qu’ils ne le font pas.