NP-difficile

Domaine

Algorithme
Théorie de la complexité
Coulombe

Définition

En théorie de la complexité, la classe de complexité NP-difficile regroupe l'ensemble de tous les problèmes de décision qui sont, de manière informelle, «au moins aussi difficiles» que les problèmes les plus difficiles dans les problèmes de la classe NP.

Français

NP-difficile

Source:

https://fr.wikipedia.org/wiki/NP-difficile

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]