« NP-difficile » : différence entre les versions


m (Remplacement de texte — « Termes privilégiés » par « Français »)
m (Remplacement de texte : « ↵<small> » par «  ==Sources== »)
 
(23 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==
[[Category:Vocabulary]]
'''NP-difficile'''   
   
   
== Définition ==
==Anglais==
'''NP-hardness'''




==Sources==


== Français ==
[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/>

Dernière version du 28 janvier 2024 à 11: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)

Récupérée de « https://datafranca.org/wiki/index.php?title=NP-difficile&oldid=90801 »


Contributeurs: Claude Coulombe, Jacques Barolet, wiki