Conseil (informatique théorique)
# Conseil (informatique théorique)

En théorie de la complexité, un conseil est une entrée supplémentaire passée à une machine de Turing qui dépend de la taille de l'entrée, afin d'aider la machine à reconnaître un langage. Cette notion est introduite par Richard Karp et Richard J. Lipton en 1982.

## Définitions

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

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

    ${\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.

## Résultats

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

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