Balise : Éditeur de wikicode 2017 |
|
| (20 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''' |
| En théorie de la complexité, la classe de complexité NP-difficile (non déterministe, temps polynomial) 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. Plus précisément, un problème H est NP-difficile 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)
