NP-difficile

Domaine

Algorithme
Théorie de la complexité
Coulombe

Définition

La dureté NP (dureté polynomiale non déterministe en temps réel), dans la théorie de la complexité informatique, est la propriété définissant une classe de problèmes qui sont, de manière informelle, " au moins aussi durs que les problèmes les plus difficiles dans les NP ". Plus précisément, un problème H est NP-dur quand chaque problème L dans NP peut être réduit en temps polynomial à H ; c'est-à-dire, en supposant qu'une solution pour H prend 1 unité de temps, nous pouvons utiliser la solution de H pour résoudre L en temps polynomial[1][2] En conséquence, trouver un algorithme polynomial pour résoudre tout problème NP-dur donnera des algorithmes polynômes pour tous les problèmes NP, qui est peu probable puisque plusieurs d'entre eux sont considérés difficiles[3].

Une idée fausse courante est que le NP dans "NP-hard" signifie "non-polynomial" alors qu'en fait il signifie "Non-deterministic Polynomial acceptable problems"[4] Bien que l'on soupçonne qu'il n'existe aucun algorithme de temps polynomial pour les problèmes NP-hard, cela n'a pas été prouvé[5] De plus, la classe P dans laquelle tous les problèmes peuvent être résolus en temps polynomial est contenue dans la classe NP[6].

Anglais

NP-hardness

NP-hardness (non-deterministic polynomial-time hardness), in computational complexity theory, is the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP". More precisely, a problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H; that is, assuming a solution for H takes 1 unit time, we can use H‎'s solution to solve L in polynomial time.[1][2] As a consequence, finding a polynomial algorithm to solve any NP-hard problem would give polynomial algorithms for all the problems in NP, which is unlikely as many of them are considered hard.[3]

A common misconception is that the NP in "NP-hard" stands for "non-polynomial" when in fact it stands for "Non-deterministic Polynomial acceptable problems".[4] Although it is suspected that there are no polynomial-time algorithms for NP-hard problems, this has not been proven.[5] Moreover, the class P in which all problems can be solved in polynomial time, is contained in the NP class.[6]