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

Étant donnés une fonction   et une classe de complexité  , la classe   est l'ensemble des langages   tels qu'il existe un langage   et une suite de conseils   de taille   tels que pour toute entrée   de taille  ,   si et seulement si  .

Étant donnés un ensemble   de fonctions   et une classe de complexité  , on définit :

 

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

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

  • si   alors   ;
  •   ;
  • d'après le théorème de Karp-Lipton, si   alors   : la hiérarchie polynomiale s'effondre au second niveau.

Notes et références modifier

Références modifier

  1. (en) Richard Karp et Richard J. Lipton, « Turing machines that take advice », L'Enseignement mathématique, vol. 28,‎ , p. 191-209 (lire en ligne)

Bibliographie modifier