P/poly

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

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

• la taille de ${\displaystyle {\mathcal {C}}_{n}}$ est au plus ${\displaystyle p(n)}$ ;
• pour tout ${\displaystyle x\in \left\{0,1\right\}^{*}}$, ${\displaystyle x\in L}$ si et seulement si ${\displaystyle {\mathcal {C}}_{n}[x]}$ est vrai, où ${\displaystyle n}$ est la taille de ${\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}$ 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}$ un langage indécidable sur l'alphabet ${\displaystyle \{0,1\}}$, et ${\displaystyle U}$ le langage des mots ${\displaystyle 1^{n}}$ (autrement dit, ${\displaystyle n}$ écrit en unaire) tels que ${\displaystyle n}$, écrit en binaire, est dans ${\displaystyle L}$. Il est clair que ${\displaystyle U}$ est indécidable, pourtant il a des circuits polynomiaux : si ${\displaystyle n}$ est dans ${\displaystyle L}$, alors ${\displaystyle {\mathcal {C}}_{n}}$ est la conjonction des ${\displaystyle n}$ bits d'entrée ; sinon ${\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}}}$, et on a même PSPACE = MA
• Si EXPSPACE est inclus dans P/poly, alors EXPSPACE ${\displaystyle =\Sigma _{2}^{\rm {P}}}$ (c'est le théorème de Meyer), et on a même EXPSPACE = MA.