|
|
| (21 versions intermédiaires par 3 utilisateurs non affichées) |
| Ligne 1 : |
Ligne 1 : |
| | ==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. |
|
| |
|
| == Domaine == | | ==Français== |
| | | '''NP-difficile''' |
| [[Category:Vocabulary]]<br>
| |
| [[Category:Algorithme]]Algorithme<br>
| |
| [[Catégorie:Théorie de la complexité]]Théorie de la complexité<br>
| |
| [[Category:Coulombe]]Coulombe<br>
| |
| [[Catégorie:Scotty]]<br>
| |
| | | |
| == Définition == | | ==Anglais== |
| | | '''NP-hardness''' |
| 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].
| |
|
| |
|
| == Français == | | ==Sources== |
|
| |
|
| | | [https://fr.wikipedia.org/wiki/NP-difficile Source: Wikipedia] |
|
| |
| == Anglais ==
| |
|
| |
|
| === NP-hardness ===
| | [[Utilisateur:Claude COULOMBE | source : Claude Coulombe]] ([[Discussion utilisateur:Claude COULOMBE | discussion]]) |
| 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]
| |
|
| |
|
| <br/>
| | [[Category:GRAND LEXIQUE FRANÇAIS]] |
| <br/>
| |
| <br/>
| |
| <br/>
| |
| <br/>
| |
| <br/>
| |
| <br/>
| |
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
Anglais
NP-hardness
Sources
Source: Wikipedia
source : Claude Coulombe ( discussion)
