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.

Notes et références

Bibliographie

• (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).