« NP (complexité) » : différence entre les versions

Version du 24 mai 2019 à 17:12

Domaine

Algorithme
Théorie de la complexité

Définition

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.

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.

Français

NP (complexité) n.f.

Anglais

NP (complexity)

source : Claude Coulombe ( discussion)

@@ Ligne 14 : / Ligne 14 : @@
 ==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.
+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.
+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==