title: Conseil (informatique théorique)
text: # 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.
  