« NP-complétude » : différence entre les versions


m (Pitpitt a déplacé la page NP-completeness vers NP-complétude)
Aucun résumé des modifications
Ligne 1 : Ligne 1 :


== Domaine ==
==Domaine==
[[Category:Vocabulary]]<br>
[[Category:Vocabulary]]
[[Category:Algorithme]]Algorithme<br>
<br>
[[Catégorie:Théorie de la complexité]]Théorie de la complexité<br>  
[[Category:Algorithme]]
[[Category:Coulombe]]Coulombe<br>  
Algorithme<br>
[[Catégorie:Scotty]]<br>  
[[Catégorie:Théorie de la complexité]]
Théorie de la complexité<br>  
[[Category:Coulombe]]
Coulombe<br>  
[[Catégorie:Scotty]]
<br>  


== Définition ==
==Définition==


En théorie de la complexité, la NP-complétude concerne l'étude des problèmes de la classe de complexité NP-complet, des problèmes qui appartiennent à la fois à la classe de complexité NP et à la classe de complexité NP-difficile.  
En théorie de la complexité, la NP-complétude concerne l'étude des problèmes de la classe de complexité NP-complet, des problèmes qui appartiennent à la fois à la classe de complexité NP et à la classe de complexité NP-difficile.  
Ligne 13 : Ligne 18 :
Bien que toute solution d'un problème NP-complet puisse être vérifiée rapidement (en temps polynomial), il n'existe aucun moyen efficace connu pour trouver une première solution. Un exemple classique de problème NP-complet est le problème du voyageur de commerce, dont le but est de déterminer le trajet le plus court pour visiter un grand nombre de villes. La difficulté d'un problème NP-complet provient du fait qu’il n’existe pas d’algorithme connu pour trouver une solution rapidement.  
Bien que toute solution d'un problème NP-complet puisse être vérifiée rapidement (en temps polynomial), il n'existe aucun moyen efficace connu pour trouver une première solution. Un exemple classique de problème NP-complet est le problème du voyageur de commerce, dont le but est de déterminer le trajet le plus court pour visiter un grand nombre de villes. La difficulté d'un problème NP-complet provient du fait qu’il n’existe pas d’algorithme connu pour trouver une solution rapidement.  


== Français ==
==Français==


NP-complétude
NP-complétude
Ligne 19 : Ligne 24 :
NP-complet
NP-complet


Source:
==Anglais==


http://www.uqac.ca/rebaine/8INF806/NPcompletudecours.pdf
===NP-completeness===


== Anglais ==


=== NP-completeness ===
<br />
In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes. In this context, NP stands for "nondeterministic polynomial time". The set of NP-complete problems is often denoted by NP-C or NPC.
<br />
 
<br />
Although any given solution to an NP-complete problem can be verified quickly (in polynomial time), there is no known efficient way to locate a solution in the first place; the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a consequence, determining whether it is possible to solve these problems quickly, called the P versus NP problem, is one of the principal unsolved problems in computer science today.
<br />
Source:


<br/>
http://www.uqac.ca/rebaine/8INF806/NPcompletudecours.pdf<br />
<br/>
<br />
<br/>
<br />
<br/>
<br/>
<br/>
<br/>

Version du 23 mai 2019 à 18:38

Domaine


Algorithme
Théorie de la complexité
Coulombe

Définition

En théorie de la complexité, la NP-complétude concerne l'étude des problèmes de la classe de complexité NP-complet, des problèmes qui appartiennent à la fois à la classe de complexité NP et à la classe de complexité NP-difficile.

Bien que toute solution d'un problème NP-complet puisse être vérifiée rapidement (en temps polynomial), il n'existe aucun moyen efficace connu pour trouver une première solution. Un exemple classique de problème NP-complet est le problème du voyageur de commerce, dont le but est de déterminer le trajet le plus court pour visiter un grand nombre de villes. La difficulté d'un problème NP-complet provient du fait qu’il n’existe pas d’algorithme connu pour trouver une solution rapidement.

Français

NP-complétude

NP-complet


Anglais

NP-completeness





Source:

http://www.uqac.ca/rebaine/8INF806/NPcompletudecours.pdf


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

Contributeurs: Claude Coulombe, Jacques Barolet, wiki