P/poly

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

En informatique théorique, plus précisément en théorie de la complexité, P/poly est la classe de problèmes de décision décidés par une famille de circuits booléens de tailles polynomiales.

Définition[modifier | modifier le code]

Famille de circuits[modifier | modifier le code]

Une famille de circuits est une suite infinie , , ..., , ... où est un circuit booléen bits d'entrée. Lorsque est une chaîne de bits de longueur , on notera le résultat de l'évaluation du circuit lorsque le ème bit d'entrée de est affecté à la valeur du ème bit de , pour tout .

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

La classe P/poly est la classe des langages tels qu'il existe une famille de circuits et un polynôme tels que :

  • la taille de est au plus  ;
  • pour tout , si et seulement si est vrai, où est la taille de .

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 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 un langage indécidable sur l'alphabet , et le langage des mots (autrement dit, écrit en unaire) tels que , écrit en binaire, est dans . Il est clair que est indécidable, pourtant il a des circuits polynomiaux : si est dans , alors est la conjonction des bits d'entrée ; sinon 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 (Adleman 1978), énonce que BPP est inclus dans P/poly[1].

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 :

  • Si NP est inclus dans P/poly, alors la hiérarchie polynomiale s'effondre au niveau 2 (c'est le théorème de Karp-Lipton (Karp et Lipton 1980)), et de plus, on a AM = MA.
  • Si PSPACE est inclus dans P/poly, alors PSPACE , et on a même PSPACE = MA
  • Si EXPSPACE est inclus dans P/poly, alors EXPSPACE (c'est le théorème de Meyer), et on a même EXPSPACE = MA.

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

  1. Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 625 (« Circuits et algorithmes probabilistes »), p. 163

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, , 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, , 302-309 p.

Lien externe[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). (en) La classe P/poly sur le Complexity Zoo