« NP (complexité) » : différence entre les versions
Aucun résumé des modifications Balise : Éditeur de wikicode 2017 |
Aucun résumé des modifications |
||
| Ligne 1 : | Ligne 1 : | ||
==Domaine== | ==Domaine== | ||
[[Category:Algorithme]] | [[Category:Algorithme]] | ||
| Ligne 14 : | Ligne 13 : | ||
==Définition== | ==Définition== | ||
La classe '''NP''' est une classe très importante de la théorie de la complexité. L'abréviation '''NP''' signifie « non déterministe polynomial » (''nondeterministic polynomial time''). Un problème de décision est dans '''NP''' s'il est décidé par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l'entrée. Intuitivement, cela revient à dire qu'on peut vérifier « rapidement » (complexité polynomiale) si une solution candidate est bien solution. Par exemple, considérons le problème de décision du voyageur de commerce qui, étant donné un entier ''k'' et un ensemble de villes séparées par des distances, détermine s'il existe un circuit de longueur inférieure à ''k'' qui passe une et une seule fois par toutes les villes. On vérifie « rapidement » qu'une solution candidate, ici un chemin quelconque, est bien solution, c'est-à-dire que c'est bien un circuit de longueur inférieur à ''k'' et qu'il passe bien une et seule fois par toutes les villes. | |||
L'un des grands problèmes ouverts de l'informatique théorique est le problème P = NP. | |||
En théorie de la complexité, la classe de complexité NP (non déterministe, temps polynomial) regroupe l'ensemble de tous les problèmes de décision pour lesquels une solution peut être vérifiée en un temps polynomial, par contre le calcul de la solution peut prendre un temps infiniment long. | En théorie de la complexité, la classe de complexité NP (non déterministe, temps polynomial) regroupe l'ensemble de tous les problèmes de décision pour lesquels une solution peut être vérifiée en un temps polynomial, par contre le calcul de la solution peut prendre un temps infiniment long. | ||
Version du 24 mai 2019 à 16:06
Domaine
Algorithme
Théorie de la complexité
Définition
La classe NP est une classe très importante de la théorie de la complexité. L'abréviation NP signifie « non déterministe polynomial » (nondeterministic polynomial time). Un problème de décision est dans NP s'il est décidé par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l'entrée. Intuitivement, cela revient à dire qu'on peut vérifier « rapidement » (complexité polynomiale) si une solution candidate est bien solution. Par exemple, considérons le problème de décision du voyageur de commerce qui, étant donné un entier k et un ensemble de villes séparées par des distances, détermine s'il existe un circuit de longueur inférieure à k qui passe une et une seule fois par toutes les villes. On vérifie « rapidement » qu'une solution candidate, ici un chemin quelconque, est bien solution, c'est-à-dire que c'est bien un circuit de longueur inférieur à k et qu'il passe bien une et seule fois par toutes les villes.
L'un des grands problèmes ouverts de l'informatique théorique est le problème P = NP.
En théorie de la complexité, la classe de complexité NP (non déterministe, temps polynomial) regroupe l'ensemble de tous les problèmes de décision pour lesquels une solution peut être vérifiée en un temps polynomial, par contre le calcul de la solution peut prendre un temps infiniment long.
Français
NP (complexité) n.f.
Anglais
NP (complexity)
Contributeurs: Claude Coulombe, Jacques Barolet, wiki
