P/poly

En informatique théorique, plus précisément en théorie de la complexité, P/poly est la classe de problèmes de décision décidés par une famille de circuits booléens de tailles polynomiales. Cette classe a été introduite par Karp et Lipton en 1980^[1] . Cette classe est importante, car comme P est incluse dans P/poly, si on démontre que NP ⊈ P/poly, alors on résout le problème ouvert P est différent de NP ^[2] .

Il y a deux définitions équivalentes, la première donnée avec le modèle de calcul des circuits booléens^[3] , l'autre avec des machines de Turing^[4] .

Une famille de circuits ${\displaystyle {\mathcal {C}}}${\displaystyle {\mathcal {C}}} est une suite infinie ${\displaystyle {\mathcal {C}}_{0}}${\displaystyle {\mathcal {C}}_{0}}, ${\displaystyle {\mathcal {C}}_{1}}${\displaystyle {\mathcal {C}}_{1}}, ..., ${\displaystyle {\mathcal {C}}_{n}}${\displaystyle {\mathcal {C}}_{n}}, ... où ${\displaystyle {\mathcal {C}}_{n}}${\displaystyle {\mathcal {C}}_{n}} est un circuit booléen ${\displaystyle n}${\displaystyle n} bits d'entrée. Lorsque ${\displaystyle x}${\displaystyle x} est une chaîne de bits de longueur ${\displaystyle n}${\displaystyle n}, on notera ${\displaystyle {\mathcal {C}}_{n}\left[x\right]}${\displaystyle {\mathcal {C}}_{n}\left[x\right]} le résultat de l'évaluation du circuit ${\displaystyle {\mathcal {C}}_{n}}${\displaystyle {\mathcal {C}}_{n}} lorsque le ${\displaystyle i}${\displaystyle i}^ème bit d'entrée de ${\displaystyle {\mathcal {C}}_{n}}${\displaystyle {\mathcal {C}}_{n}} est affecté à la valeur du ${\displaystyle i}${\displaystyle i}^ème bit de ${\displaystyle x}${\displaystyle x}, pour tout ${\displaystyle i\in \{1,2,...,n\}}${\displaystyle i\in \{1,2,...,n\}}.

La classe P/poly est la classe des langages ${\displaystyle L\subseteq \{0,1\}^{*}}${\displaystyle L\subseteq \{0,1\}^{*}} tels qu'il existe une famille de circuits ${\displaystyle {\mathcal {C}}}${\displaystyle {\mathcal {C}}} et un polynôme ${\displaystyle p}${\displaystyle p} tels que :

• la taille de ${\displaystyle {\mathcal {C}}_{n}}${\displaystyle {\mathcal {C}}_{n}} est au plus ${\displaystyle p(n)}${\displaystyle p(n)} ;
• pour tout ${\displaystyle x\in \left\{0,1\right\}^{*}}${\displaystyle x\in \left\{0,1\right\}^{*}}, ${\displaystyle x\in L}${\displaystyle x\in L} si et seulement si ${\displaystyle {\mathcal {C}}_{n}[x]}${\displaystyle {\mathcal {C}}_{n}[x]} est vrai, où ${\displaystyle n}${\displaystyle n} est la taille de ${\displaystyle x}${\displaystyle x}.

On dit d'un langage satisfaisant cette propriété qu'il a des circuits polynomiaux.

On peut définir P/poly de manière équivalente en utilisant des machines de Turing déterministes qui prennent conseil. Une telle machine, a le droit d'utiliser un mot fini c_n, qui sert de conseil pour traiter toutes les instances x de taille n. Un problème est dans P/poly s'il existe une machine de Turing M en temps polynomial et une suite de mots finis c₀, c₁, c₂,... où c_n est de taille polynomiale en n, tels que pour tout mot x de longueur n, x est une instance positive ssi M(x, c_n) = 1. Les mots finis c₀, c₁, c₂,... s'appellent des conseils.

La classe P est incluse dans la classe P/poly (P peut être définie comme P/poly sauf avec des familles de circuits uniformes en temps polynomial). P/poly contient des problèmes décidables et hors de P^{[réf. nécessaire]} .

Remarquons qu'il n'est pas nécessaire que le circuit correspondant à une entrée de taille ${\displaystyle n}${\displaystyle n} puisse être construit en temps polynomial, ni même de façon déterministe. Cela a une conséquence étrange : il existe des langages indécidables qui ont des circuits polynomiaux. En effet, soit ${\displaystyle L}${\displaystyle L} un langage indécidable sur l'alphabet ${\displaystyle \{0,1\}}${\displaystyle \{0,1\}}, et ${\displaystyle U}${\displaystyle U} le langage des mots ${\displaystyle 1^{n}}${\displaystyle 1^{n}} (autrement dit, ${\displaystyle n}${\displaystyle n} écrit en unaire) tels que ${\displaystyle n}${\displaystyle n}, écrit en binaire, est dans ${\displaystyle L}${\displaystyle L}. Il est clair que ${\displaystyle U}${\displaystyle U} est indécidable, pourtant il a des circuits polynomiaux : si ${\displaystyle n}${\displaystyle n} est dans ${\displaystyle L}${\displaystyle L}, alors ${\displaystyle {\mathcal {C}}_{n}}${\displaystyle {\mathcal {C}}_{n}} est la conjonction des ${\displaystyle n}${\displaystyle n} bits d'entrée ; sinon ${\displaystyle {\mathcal {C}}_{n}}${\displaystyle {\mathcal {C}}_{n}} est juste le booléen faux.

Le théorème d'Adleman, démontré par Leonard Adleman (Adleman 1978), énonce que BPP est inclus dans P/poly^[5] .

P/poly a une place importante en théorie de la complexité : plusieurs propriétés importantes s'expriment à l'aide de P/poly :

• Si NP est inclus dans P/poly, alors la hiérarchie polynomiale s'effondre au niveau 2 (c'est le théorème de Karp-Lipton (Karp et Lipton 1980)), et de plus, on a AM = MA .
• Si NP n'est pas inclus dans P/poly, comme P l'est, on en déduit que P est différent de NP.
• Si PSPACE est inclus dans P/poly, alors PSPACE ${\displaystyle =\Sigma _{2}^{\rm {P}}}${\displaystyle =\Sigma _{2}^{\rm {P}}}, et on a même PSPACE = MA
• Si EXPSPACE est inclus dans P/poly, alors EXPSPACE ${\displaystyle =\Sigma _{2}^{\rm {P}}}${\displaystyle =\Sigma _{2}^{\rm {P}}} (c'est le théorème de Meyer), et on a même EXPSPACE = MA.

Il y a équivalence^[6] entre :

1. Un langage A est dans P/poly
2. il existe un langage creux S tel que A est réductible au sens de Turing en temps polynomial à S,
3. il existe un langage unaire T tel que A est réductible au sens de Turing en temps polynomial à T.

L'équivalence entre 1 et 2 est attribué à A. Meyer selon ^[7] (comme indiqué dans ^[6] ) et l'équivalence entre 2 et 3 est montré dans ^[8] .

• Jean Goubault-Larrecq, Classes de complexité randomisées, [(fr) lire en ligne]

• (en) Leonard M. Adleman, « Two theorems on random polynomial time », dans Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computer Science, 1978, 75–83 p. (DOI 10.1109/SFCS.1978.37 )

• (en) Richard M. Karp et Richard J. Lipton, « Some Connections between Nonuniform and Uniform Complexity Classes », dans Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA, 1980, 302-309 p.

(en) La classe P/poly sur le Complexity Zoo

• icône décorative Portail de l'informatique théorique

• Classe de complexité

• Article à référence nécessaire
• Portail:Informatique théorique/Articles liés
• Portail:Informatique/Articles liés
• Portail:Mathématiques/Articles liés
• Portail:Sciences/Articles liés