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}\to \mathbb{N}$ et une classe de complexité $𝖢$, la classe $𝖢/f(n)$ est l'ensemble des langages $A$ tels qu'il existe un langage $B\in 𝖢$ 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 $ℱ$ de fonctions $f:\mathbb{N}\to \mathbb{N}$ et une classe de complexité $𝖢$, on définit :

$𝖢/ℱ=\bigcup _{f\in ℱ}𝖢/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 $𝖭𝖯\subseteq 𝖯/𝗅𝗈𝗀$ alors $𝖯=𝖭𝖯$ ;

• $𝖼𝗈𝖭𝖤𝖷𝖯𝖳𝖨𝖬𝖤\subseteq 𝖭𝖤𝖷𝖯𝖳𝖨𝖬𝖤/𝗅𝗂𝗇$ ;

• d'après le théorème de Karp-Lipton, si $𝖭𝖯\subseteq 𝖯/𝗉𝗈𝗅𝗒$ alors ${\mathrm{\Sigma }}_2^{𝖯}={\mathrm{\Pi }}_2^{𝖯}=𝖯𝖧$ : la hiérarchie polynomiale s'effondre au second niveau.

Notes et références

Bibliographie

• Modèle:Ouvrage
• Modèle:Ouvrage