|
|
| (17 versions intermédiaires par 2 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 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== | | ==Sources== |
|
| |
|
| NP-difficile
| | [https://fr.wikipedia.org/wiki/NP-difficile Source: Wikipedia] |
|
| |
| Source:
| |
|
| |
| https://fr.wikipedia.org/wiki/NP-difficile | |
| | |
| ==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 />
| |
Dernière version du 28 janvier 2024 à 10:43
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)
