Ê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 GraphSearch.
Concept
P (complexité)
Résumé
La classe P, aussi noté parfois PTIME ou DTIME(nO(1)), est une classe très importante de la théorie de la complexité, un domaine de l'informatique théorique et des mathématiques. Par définition, un problème de décision est dans P s'il est décidé par une machine de Turing déterministe en temps polynomial par rapport à la taille de l'entrée. On dit que le problème est décidé en temps polynomial.
Les problèmes dans P sont considérés comme « faisables » (feasible en anglais), faciles à résoudre (dans le sens où on peut le faire relativement rapidement). C'est la thèse de Cobham émise par le scientifique américain Alan Cobham. René Lalement attribue cette thèse à Cook. La classe P est incluse dans la classe NP, conduisant à l'un des grands problèmes ouverts de la théorie de la complexité, à savoir : P est-il égal à NP ?
Un problème est dans P s'il existe un algorithme qui le décide en temps polynomial. Citons :
les restrictions 2SAT et HORNSAT du problème SAT sont dans P.
Connexité dans un graphe : Un exemple de problème polynomial est celui de la connexité dans un graphe. Étant donné un graphe à n sommets (on considère que la taille de la donnée, donc du graphe, est son nombre de sommets), il s'agit de savoir si toutes les paires de sommets sont reliées par un chemin. Un algorithme de parcours en profondeur construit un arbre couvrant du graphe à partir d'un sommet. Si cet arbre contient tous les sommets du graphe, alors le graphe est connexe. Le temps nécessaire pour construire cet arbre est au plus c.n2 (où c est une constante et n le nombre de sommets du graphe), donc le problème est dans la classe P.
Aussi, parfois la preuve de l'appartenance à P, qui se fait généralement par la découverte d'un algorithme polynomial, a demandé des années de recherche :
Le test de primalité AKS est un algorithme qui montre que le problème de savoir si un entier est premier ou non peut être résolu par un algorithme polynomial.
Programmation linéaire : Les algorithmes de points intérieurs permettent de classer la programmation linéaire dans la classe P.
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.