« NP-difficile » : différence entre les versions
m (Claude COULOMBE a déplacé la page NP-hard vers NP-hardness par-dessus une redirection) |
Aucun résumé des modifications Balise : Éditeur de wikicode 2017 |
||
| Ligne 1 : | Ligne 1 : | ||
== Domaine == | ==Domaine== | ||
[[Category:Vocabulary]]<br> | [[Category:Vocabulary]]<br> | ||
| Ligne 6 : | Ligne 6 : | ||
[[Catégorie:Théorie de la complexité]]Théorie de la complexité<br> | [[Catégorie:Théorie de la complexité]]Théorie de la complexité<br> | ||
[[Category:Coulombe]]Coulombe<br> | [[Category:Coulombe]]Coulombe<br> | ||
[[Catégorie:Scotty]]<br> | [[Catégorie:Scotty]] | ||
<br> | |||
== Définition == | ==Définition== | ||
En théorie de la complexité, la classe de complexité NP-difficile | 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== | |||
== Français == | |||
NP-difficile | |||
Source: | |||
https://fr.wikipedia.org/wiki/NP-difficile | |||
== Anglais == | ==Anglais== | ||
=== NP-hardness === | ===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] | 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] | 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/> | <br /> | ||
<br/> | <br /> | ||
<br/> | <br /> | ||
<br/> | <br /> | ||
<br/> | <br /> | ||
<br/> | <br /> | ||
<br/> | <br /> | ||
Version du 30 avril 2019 à 00:43
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]
Contributeurs: Claude Coulombe, Jacques Barolet, wiki
