NP-complétude

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

Source:

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

Anglais

NP-completeness

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.

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.