P/poly

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. Cette classe a été introduite par Karp et Lipton en 1980[1]. Cette classe est importante, car comme P est incluse dans P/poly, si on démontre que NPP/poly, alors on résout le problème ouvert P est différent de NP[2].

Définitions

Il y a deux définitions équivalentes, la première donnée avec le modèle de calcul des circuits booléens[3], l'autre avec des machines de Turing[4].

Définition par circuits

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 .

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.

Définition par machine de Turing avec conseils

On peut définir P/poly de manière équivalente en utilisant des machines de Turing déterministes qui prennent conseil. Une telle machine, a le droit d'utiliser un mot fini cn, qui sert de conseil pour traiter toutes les instances x de taille n. Un problème est dans P/poly s'il existe une machine de Turing M en temps polynomial et une suite de mots finis c0, c1, c2,... où cn est de taille polynomiale en n, tels que pour tout mot x de longueur n, x est une instance positive ssi M(x, cn) = 1. Les mots finis c0, c1, c2,... s'appellent des conseils.

Propriétés

P/poly et P

La classe P est incluse dans la classe P/poly (P peut être définie comme P/poly sauf avec des familles de circuits uniformes en temps polynomial). P/poly contient des problèmes décidables et hors de P[réf. nécessaire].

P/poly contient des langages indécidables

Remarquons qu'il n'est pas nécessaire que le circuit correspondant à une entrée de taille puisse être construit en temps polynomial, 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

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

Importance de P/poly

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 NP n'est pas inclus dans P/poly, comme P l'est, on en déduit que P est différent de NP.
  • 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.

Caractérisation

Il y a équivalence[6] entre :

  1. Un langage A est dans P/poly
  2. il existe un langage creux S tel que A est réductible au sens de Turing en temps polynomial à S,
  3. il existe un langage unaire T tel que A est réductible au sens de Turing en temps polynomial à T.

L'équivalence entre 1 et 2 est attribué à A. Meyer selon [7] (comme indiqué dans [6]) et l'équivalence entre 2 et 3 est montré dans [8].

Référence

  1. Richard M. Karp et Richard J. Lipton, « Some Connections Between Nonuniform and Uniform Complexity Classes », Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, ACM, sTOC '80, , p. 302–309 (ISBN 9780897910170, DOI 10.1145/800141.804678, lire en ligne, consulté le )
  2. (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, (ISBN 0-521-42426-7), chap. 6 Boolean circuits »), p. 6.5
  3. (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, (ISBN 0-521-42426-7), chap. 6 Boolean circuits »), p. 108, Def. 6.5
  4. (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, (ISBN 0-521-42426-7), chap. 6 Boolean circuits »), p. 6.3, Th. 6.18
  5. Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 625 (« Circuits et algorithmes probabilistes »), p. 163
  6. (en) Ronald V. Book, « On Sets with Small Information Content », dans Kolmogorov Complexity and Computational Complexity, Springer Berlin Heidelberg, coll. « EATCS Monographs on Theoretical Computer Science », (ISBN 9783642777356, DOI 10.1007/978-3-642-77735-6_3, lire en ligne), p. 23–42
  7. L. Berman et J. Hartmanis, « On Isomorphisms and Density of $NP$ and Other Complete Sets », SIAM Journal on Computing, vol. 6, no 2, , p. 305–322 (ISSN 0097-5397, DOI 10.1137/0206023, lire en ligne, consulté le )
  8. (en-GB) José Luis Balcázar, Josep Díaz et Joaquim Gabarró, Structural Complexity I, coll. « EATCS Monographs on Theoretical Computer Science Series », (DOI 10.1007/978-3-642-97062-7, lire en ligne)

Bibliographie

  • Jean Goubault-Larrecq, Classes de complexité randomisées, [(fr) lire en ligne]
  • (en) Leonard M. 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) Richard M. Karp et Richard J. 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

(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


  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.