P/poly

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La classe P/poly, est un objet de la théorie de la complexité, en informatique théorique. C'est une classe de problèmes de décision.

Définition[modifier | modifier le code]

Une définition préliminaire : famille de circuits[modifier | modifier le code]

Une famille de circuits \mathcal{C} est une suite infinie \mathcal{C}_0, \mathcal{C}_1, ..., \mathcal{C}_n, ... de circuits booléens, où \mathcal{C}_n a n bits d'entrée. Lorsque x est une chaîne de bits de longueur n, on notera \mathcal{C}_n\left[x\right] le résultat de l'évaluation du circuit \mathcal{C}_n lorsque le ième bit d'entrée de \mathcal{C}_n est affecté à la valeur du ième bit de x.

Définition de P/poly[modifier | modifier le code]

La classe P/poly est la classe des langages L \subseteq \{ 0, 1 \}^* tels qu'il existe une famille de circuits \mathcal{C} telle que :

  • la taille de \mathcal{C}_n est au plus p(n), où p(n) est un polynôme en n ;
  • pour tout x\in\left\{0,1\right\}^*, x\in L si et seulement si \mathcal{C}_n[x] est vrai, où n est la taille de x.

On dit d'un langage satisfaisant cette propriété qu'il a des circuits polynomiaux.

Propriétés[modifier | modifier le code]

P/poly contient des langages indécidables[modifier | modifier le code]

Remarquons qu'il n'est pas nécessaire que le circuit correspondant à une entrée de taille n puisse être construit en temps polynômial, ni même de façon déterministe. Cela a une conséquence étrange : il existe des langages indécidables qui ont des circuits polynomiaux. En effet, soit L un langage indécidable sur l'alphabet \{0,1\}, et U le langage des mots 1^n (autrement dit, n écrit en unaire) tels que n, écrit en binaire, est dans L. Il est clair que U est indécidable, pourtant il a des circuits polynomiaux : si n est dans L, alors \mathcal{C}_n est la conjonction des n bits d'entrée ; sinon \mathcal{C}_n est juste le booléen faux.

Théorème d'Adleman[modifier | modifier le code]

Le théorème d'Adleman, démontré par Leonard Adleman, énonce que BPP est inclus dans P/poly (Adleman 1978).

Importance de P/poly[modifier | modifier le code]

P/poly a une place importante en théorie de la complexité : plusieurs propriétés importantes s'expriment à l'aide de P/poly :

Bibliographie[modifier | modifier le code]

  • Jean Goubault-Larrecq, Classes de complexité randomisées, [(fr) lire en ligne]
  • (en) Adleman, « Two theorems on random polynomial time », dans Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computer Science,‎ 1978, 75–83 p. (DOI 10.1109/SFCS.1978.37)
  • (en) Karp et Lipton, « Some Connections between Nonuniform and Uniform Complexity Classes », dans Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA,‎ 1980, 302-309 p.

Lien externe[modifier | modifier le code]

(en) La classe P/poly sur le Complexity Zoo

Référence[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « P/poly » (voir la liste des auteurs)