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^[1].

Définitions[modifier | modifier le code]

É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[modifier | modifier le code]

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.