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.

• (en) Sanjeev Arora et Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 20 avril 2009, 579 p. (ISBN 978-0-521-42426-4, lire en ligne). 
• Sylvain Perifel, Complexité algorithmique, Éditions Ellipses, 22 avril 2014, 432 p. (ISBN 978-2-729-88692-9, lire en ligne). 

• Portail de l'informatique théorique