Conseil (informatique théorique)

Étant donnés une fonction ${\displaystyle f:\mathbb {N} \rightarrow \mathbb {N} }$ et une classe de complexité ${\displaystyle {\mathsf {C}}}$, la classe ${\displaystyle {\mathsf {C}}/f(n)}$ est l'ensemble des langages ${\displaystyle A}$ tels qu'il existe un langage ${\displaystyle B\in {\mathsf {C}}}$ et une suite de conseils ${\displaystyle (a_{n})}$ de taille ${\displaystyle f(n)}$ tels que pour toute entrée ${\displaystyle x}$ de taille ${\displaystyle n}$, ${\displaystyle x\in A}$ si et seulement si ${\displaystyle (x,a_{n})\in B}$.

Étant donnés un ensemble ${\displaystyle {\mathcal {F}}}$ de fonctions ${\displaystyle f:\mathbb {N} \rightarrow \mathbb {N} }$ et une classe de complexité ${\displaystyle {\mathsf {C}}}$, on définit :

${\displaystyle {\mathsf {C}}/{\mathcal {F}}=\bigcup \limits _{f\in {\mathcal {F}}}{\mathsf {C}}/f(n)}$

Une classe importante est la classe P/poly, qui est donc l'ensemble des problèmes de décision décidés en temps polynomial avec un conseil de taille polynomiale. P/poly est en fait également la classe des problèmes de décision décidés par une famille de circuits booléens de tailles polynomiales.

Quelques exemples de résultats sur les classes de complexité définies par machines de Turing avec conseils :

• si ${\displaystyle {\mathsf {NP}}\subseteq {\mathsf {P}}/{\mathsf {log}}}$ alors ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$ ;

• ${\displaystyle {\mathsf {coNEXPTIME}}\subseteq {\mathsf {NEXPTIME}}/{\mathsf {lin}}}$ ;

• d'après le théorème de Karp-Lipton, si ${\displaystyle {\mathsf {NP}}\subseteq {\mathsf {P}}/{\mathsf {poly}}}$ alors ${\displaystyle \Sigma _{2}^{\mathsf {P}}=\Pi _{2}^{\mathsf {P}}={\mathsf {PH}}}$ : la hiérarchie polynomiale s'effondre au second niveau.