Voir la source de P (complexité)

{{Voir homonymes|Classe P}}
La classe '''P''', aussi noté parfois '''PTIME''' ou '''DTIME'''(n<sup>O(1)</sup>), est une [[classe de complexité|classe]] très importante de la [[théorie de la complexité (informatique théorique)|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 [[polynôme|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 » (''{{Langue|en|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<ref>{{Computational Complexity (Arora et Barak)|numéro chapitre = 1}} dans les notes historiques.</ref>{{,}}<ref>{{Article| auteur = Alan Cobham | année = 1965 | titre = The intrinsic computational difficulty of functions | périodique = Proceedings of the 1964 International Congress for Logic, Methodology, and Philosophy of Science| éditeur = North Holland}}.</ref>. René Lalement attribue cette thèse à Cook<ref>{{Ouvrage|auteur1=René Lalement|titre=logique réduction résolution|passage=p. 344|éditeur=Masson|date=|isbn=|lire en ligne=}}</ref>. La classe '''P''' est incluse dans la [[NP (complexité)|classe NP]], conduisant à l'un des grands problèmes ouverts de la théorie de la complexité, à savoir : [[problème P=NP|P est-il égal à NP ?]]

== Exemples de problèmes dans P ==

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''.''n''²  (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 [[Méthodes de points intérieurs|algorithmes de points intérieurs]] permettent de classer la [[optimisation linéaire|programmation linéaire]] dans la classe '''P'''. Ce problème est même [[P-complet|'''P'''-complet]]{{Référence nécessaire|date=1 novembre 2017}}.
La classe '''P''' peut être définie sur des problèmes algorithmiques généraux pour lesquels il existe une solution en temps polynomial, et pas seulement les problèmes de décision<ref>{{Ouvrage|langue=en|titre=Complexity Theory|doi=10.1007/3-540-27477-4|lire en ligne=https://link.springer.com/book/10.1007/3-540-27477-4|consulté le=2022-10-03}}</ref>, auquel cas <math>\mathrm{P} \not\subseteq \mathrm{NP}</math>, mais <math>\mathrm{P} \cap \mathrm{DEC} \subseteq \mathrm{NP}</math>, où DEC est la classe des problèmes de décision.

== Définitions formelles ==
=== Définition classique à l'aide de machines de Turing ===
On note '''TIME'''(''t''(''n'')) la classe des [[problème de décision|problèmes de décision]] qui peuvent être décidés en temps de l'ordre de grandeur de ''t''(''n'') sur une machine déterministe (où ''n'' est la taille de l'entrée). Alors par définition

:<math>\mathrm{P} = \bigcup_{c>1}\mathrm{TIME}(n^c).</math>

=== Définition avec des circuits ===
P peut aussi être défini à l'aide de familles uniformes de [[Circuit booléen|circuits booléens]]. Un langage ''L'' est dans P si, et seulement si, il existe une famille de circuits booléens <math>\{C_n:n \in \mathbb{N}\}</math>, uniforme en temps polynomial (c'est-à-dire qu'il existe une machine de Turing déterministe qui produit <math>C_n</math> sur l'entrée 1<sup>n</sup>) telle que
* pour tout <math>n \in \mathbb{N}</math>, <math>C_n</math> prend ''n'' bits en entrée et retourne un bit de sortie
* Pour tout ''x'' dans ''L'', <math>C_{|x|}(x)=1</math>
* Pour tout ''x'' qui n'est pas dans  ''L'', <math>C_{|x|}(x)=0</math>
La définition par circuits peut être affaiblie en utilisant une famille uniforme en espace logarithme et donne toujours une définition équivalente pour la classe P.{{Référence nécessaire|date=1 novembre 2017}} Si on relâche l'hypothèse d'uniformité, on définit la [[P/poly|classe P/poly]].

== Relations avec les autres classes ==
[[Image:Complexity subsets pspace.svg|upright=1|thumb|Représentations des inclusions des classes usuelles.]]
On a l'inclusion évidente  '''P''' <math>\scriptstyle \subseteq</math> '''NP''', mais l'une des grandes questions ouvertes de l'[[informatique théorique]] est le [[problème P=NP|problème P = NP ?]].

On peut placer '''P''' dans la hiérarchie des langages, classés selon l'espace requis : elle contient '''[[NL (complexité)|NL]]''' (la classe des problèmes pouvant être résolus sur une machine non-déterministe en espace logarithmique) et est contenu par '''[[PSPACE]]''' (la classe des problèmes pouvant être résolus en espace polynomial). Les inclusions sont les suivantes (on ne sait pas si elles sont strictes) :

:[[L (complexité)|'''L''']] ⊆ [[NL (complexité)|'''NL''']] ⊆ [[NC (complexité)|'''NC''']] ⊆ '''P''' ⊆ [[NP (complexité)|'''NP''']] ⊆ '''[[PSPACE]]''' ⊆ '''[[EXPTIME]]''' ⊆ '''NEXPTIME''' ⊆ '''[[EXPSPACE]]'''

:'''P''' ≠ '''[[EXPTIME]]''' (d'après le [[théorème de hiérarchie en temps déterministe]])

Par ailleurs, '''P''' est le premier niveau de la [[hiérarchie polynomiale]]. Et '''P''' est incluse dans les classes polynomiales sur des machines plus puissantes (quantiques ou utilisant du hasard par exemple), comme '''[[ZPP (complexité)|ZPP]]''', '''[[BPP (complexité)|BPP]]''' et '''[[BQP]]'''.

== Problèmes P-complets ==
Un problème de décision ''A'' est dit '''P'''-''complet'', ou ''complet pour la classe'' '''P''', s'il est dans la classe '''P''' et si tout problème de la classe '''P''' peut être réduit à ''A'' en [[complexité en espace|espace]] logarithmique (c'est-à-dire que la traduction d'une instance ''x'' du problème à une instance de ''A'' peut s'effectuer en utilisant un espace O(log |''x''|)). Les problèmes suivants sont P-[[Complet (complexité)|complets]].

* Horn-SAT : le [[problème SAT]] ''général'' est [[problème NP-complet|NP-complet]], mais sa restriction aux ensembles de [[clause de Horn|clauses de Horn]] est dans '''P'''. Il est P-complet.
* [[Problème de l'évaluation d'un circuit]]<ref>{{Article |auteur1=[[Richard E. Ladner]] |titre=The circuit value problem is log space complete for P |périodique=ACM SIGACT News |volume=7 |numéro=1 |date=1975-01-01 |issn=0163-5700 |doi=10.1145/990518.990519 |lire en ligne=http://dl.acm.org/citation.cfm?id=990518.990519 |consulté le=2018-10-30 |pages=18–20 }}</ref>{{,}}<ref name=":02">{{Lien web|titre=Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak|url=http://theory.cs.princeton.edu/complexity/|site=theory.cs.princeton.edu|date=|consulté le=2018-10-30|page=119, Th. 6.30}}</ref> : ce problème, en anglais ''circuit value problem'' (CVP), consiste à déterminer si, pour un [[circuit booléen]] donné, le résultat de la fonction réalisée sur une entrée donnée correspond à une valeur donnée.
* Le problème qui consiste à savoir si le langage dénoté par une [[grammaire algébrique]] est vide ou pas<ref>{{article
 | prénom1 = Neil D. | nom1 = Jones 
 | prénom2 = William T. | nom2 =  Laaser
 | titre     = Complete Problems for Deterministic Polynomial Time
 | périodique   = Theor. Comput. Sci.
 | volume    = 3 | numéro = 1
 | année     = 1976
 | passage     = 105-117}}.
</ref>.
* Décider si le langage d'une grammaire algébrique est infini<ref>{{Lien web|titre=math.stackexchange.com|url=https://math.stackexchange.com/questions/2394837/show-that-checking-if-context-free-grammar-generates-infinite-language-is-p-comp|date=}}</ref>.
* Le problème de [[vérification de modèles]] (''{{Langue|en|model checking}}'' en anglais) d'une formule de la [[logique temporelle]] CTL est dans P<ref>{{Article|prénom1=André|nom1=Arnold|prénom2=Paul|nom2=Crubille|titre=A Linear Algorithm to Solve Fixed-point Equations on Transition Systems|périodique=Inf. Process. Lett.|volume=29|numéro=2|date=1988-9|issn=0020-0190|doi=10.1016/0020-0190(88)90029-4|lire en ligne=http://dx.doi.org/10.1016/0020-0190(88)90029-4|consulté le=2019-02-27|pages=57–66}}</ref>{{,}}<ref>{{Article|prénom1=E. M.|nom1=Clarke|prénom2=E. A.|nom2=Emerson|prénom3=A. P.|nom3=Sistla|titre=Automatic Verification of Finite-state Concurrent Systems Using Temporal Logic Specifications|périodique=ACM Trans. Program. Lang. Syst.|volume=8|numéro=2|date=1986-4|issn=0164-0925|doi=10.1145/5397.5399|lire en ligne=http://doi.acm.org/10.1145/5397.5399|consulté le=2019-02-27|pages=244–263}}</ref> et a été prouvé P-complet <ref name=":0">{{Ouvrage|prénom1=Philippe|nom1=Schnoebelen|titre=The Complexity of Temporal Logic Model Checking|date=2002-01-01|lire en ligne=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.992|consulté le=28 juin 2016}}.</ref>. Plus précisément, la démonstration<ref name=":0" /> montre que le ''{{Langue|en|model checking}}'' d'une formule du fragment syntaxique de CTL avec les opérateurs AX (pour tout successeur) et EX (il existe un successeur) est P-difficile. Ainsi, le ''{{Langue|en|model checking}}'' d'une formule de la [[logique modale]] K est P-complet.
*Le [[Problème de flot maximum|problème du flot maximum]]<ref>{{Article|langue=en|titre=The maximum flow problem is log space complete for P|périodique=Theoretical Computer Science|volume=21|numéro=1|date=1982-10-01|issn=0304-3975|doi=10.1016/0304-3975(82)90092-5|lire en ligne=https://www.sciencedirect.com/science/article/pii/0304397582900925|consulté le=2018-11-08|pages=105–111}}</ref> et donc la [[Optimisation linéaire|programmation linéaire réelle]].

S'il existe un [[langage creux]] qui est P-complet, alors P = [[L (complexité)|LOGSPACE]]<ref>{{Article |auteur1=[[Jin-Yi Cai]] |prénom2=D. |nom2=Sivakumar |titre=Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis |périodique=Journal of Computer and System Sciences |volume=58 |numéro=2 |date=1999-04-01 |issn=0022-0000 |doi=10.1006/jcss.1998.1615 |lire en ligne=http://www.sciencedirect.com/science/article/pii/S0022000098916154 |consulté le=2019-07-14 |pages=280–296 }}</ref>.

== Propriétés supplémentaires ==
On parle dans certains cas, d'algorithmes en temps ''fortement ou faiblement polynomial''. Cette distinction existe pour les problèmes dont l'entrée contient des entiers. On parle de temps faiblement polynomial si les entiers doivent être donnés en écriture unaire (c'est-à-dire que le nombre ''n'' compte pour une taille ''n'') pour avoir un temps polynomial, et on parle de temps fortement polynomial si même l'écriture compacte (''n'' a taille log(''n'')) donne une complexité polynomiale.

== Voir aussi ==
[[NP (complexité)|Classe NP]]

[[P/poly]]

== Bibliographie ==
{{Computational Complexity (Arora et Barak)|numéro chapitre=1|titre chapitre = The computational model —and why it doesn’t matter}}

== Lien externe ==
{{Complexity Zoo|fin=P#p|nom=P}}

== Notes et références ==
<references />

{{Palette|Théorie de la complexité}}

{{Portail|informatique théorique}}

[[Catégorie:Classe de complexité]]