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. 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.

Définitions

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

Définition par circuits

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

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

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

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

Définition par machine de Turing avec conseils

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.

Propriétés

P/poly et P

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 PModèle:Référence nécessaire.

P/poly contient des langages indécidables

Remarquons qu'il n'est pas nécessaire que le circuit correspondant à une entrée de taille $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 $L$ un langage indécidable sur l'alphabet $\{0,1\}$, et $U$ le langage des mots $1^n$ (autrement dit, $n$ écrit en unaire) tels que $n$, écrit en binaire, est dans $L$. Il est clair que $U$ est indécidable, pourtant il a des circuits polynomiaux : si $n$ est dans $L$, alors ${𝒞}_n$ est la conjonction des $n$ bits d'entrée ; sinon ${𝒞}_n$ est juste le booléen faux.

Théorème d'Adleman

Le théorème d'Adleman, démontré par Leonard Adleman Modèle:Référence Harvard, énonce que BPP est inclus dans P/poly.

Importance de P/poly

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 Modèle:Référence Harvard), 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 $={\mathrm{\Sigma }}_2^{\mathrm{P}}$, et on a même PSPACE = MA
• Si EXPSPACE est inclus dans P/poly, alors EXPSPACE $={\mathrm{\Sigma }}_2^{\mathrm{P}}$ (c'est le théorème de Meyer), et on a même EXPSPACE = MA.

Caractérisation

Il y a équivalence 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 (comme indiqué dans ) et l'équivalence entre 2 et 3 est montré dans .

Bibliographie

• Jean Goubault-Larrecq, Classes de complexité randomisées, Modèle:Lire en ligne

• Modèle:Chapitre

• Modèle:Chapitre

Lien externe

Modèle:Palette Modèle:Portail