Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
NP (complexité)
Résumé
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 » (« en »). 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.
On appelle NTIME(t(n)) la classe des problèmes de décision qui peuvent être résolus en temps de l'ordre de grandeur de t(n) sur une machine de Turing non déterministe (où n est la taille de l'entrée).
Alors NP = NTIME().
Sur un alphabet , un langage est dans NP s'il existe un polynôme et une machine de Turing déterministe en temps polynomial , tels que pour un mot de taille : (où signifie que la machine accepte sur l'entrée (x,u)).
Autrement dit, il existe un « indice », appelé certificat, qui permet de prouver rapidement que le mot est dans le langage.
problème NP-complet
Les problèmes NP-complets sont les problèmes de NP qui sont aussi NP-difficiles. Ce sont les problèmes les plus difficiles de la classe dans le sens où l'on peut ramener tout problème de NP à ces problèmes par certaines réductions, en particulier des réductions polynomiales.
De nombreux problèmes ont été identifiés comme NP-complets, dont le problème SAT ou encore Circuit Hamiltonien.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.