Voir la source de P/poly

En [[informatique théorique]], plus précisément en [[théorie de la complexité (informatique théorique)|théorie de la complexité]], '''P/poly''' est la [[classe de complexité|classe]] de [[problème de décision|problèmes de décision]] décidés par une famille de [[circuit booléen|circuits booléens]] de tailles polynomiales. Cette classe a été introduite par Karp et Lipton en 1980<ref>{{Article|prénom1=Richard M.|nom1=Karp|prénom2=Richard J.|nom2=Lipton|titre=Some Connections Between Nonuniform and Uniform Complexity Classes|périodique=Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing|série=STOC '80|éditeur=ACM|date=1980|isbn=9780897910170|doi=10.1145/800141.804678|lire en ligne=http://doi.acm.org/10.1145/800141.804678|consulté le=2019-03-12|pages=302–309}}</ref>. Cette classe est importante, car comme '''P''' est incluse dans '''P/poly''', si on démontre que  '''NP''' ⊈ '''P/poly''', alors on résout le problème ouvert [[Problème P = NP|P est différent de NP]]<ref>{{Computational Complexity (Arora et Barak)|numéro chapitre=6|titre chapitre=Boolean circuits|passage=6.5}}</ref>.

== Définitions ==
Il y a deux définitions équivalentes, la première donnée avec le modèle de calcul des circuits booléens<ref>{{Computational Complexity (Arora et Barak)|numéro chapitre=6|titre chapitre=Boolean circuits|passage=p. 108, Def. 6.5}}</ref>, l'autre avec des machines de Turing<ref>{{Computational Complexity (Arora et Barak)|numéro chapitre=6|titre chapitre=Boolean circuits|passage=6.3, Th. 6.18}}</ref>.

=== Définition par circuits ===

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

La classe '''P/poly''' est la classe des langages <math>L \subseteq \{ 0, 1 \}^* </math> tels qu'il existe une famille de circuits <math>\mathcal{C}</math> et un polynôme <math>p</math> tels que :
* la taille de <math>\mathcal{C}_n</math> est au plus <math>p(n)</math> ;
* pour tout <math>x\in\left\{0,1\right\}^*</math>, <math>x\in L</math> si et seulement si <math>\mathcal{C}_n[x]</math> est vrai, où <math>n</math> est la taille de <math>x</math>.

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 [[Machine de Turing|machines de Turing]] déterministes qui prennent [[Conseil (informatique théorique)|conseil]]. Une telle machine, a le droit d'utiliser un mot fini c<sub>n</sub>, 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 c<sub>0</sub>, c<sub>1</sub>, c<sub>2</sub>,... où c<sub>n</sub> est de taille polynomiale en n, tels que pour tout mot x de longueur n, x est une instance positive ssi M(x, c<sub>n</sub>) = 1.  Les mots finis c<sub>0</sub>, c<sub>1</sub>, c<sub>2</sub>,... s'appellent des ''conseils''.

== Propriétés ==

=== P/poly et P ===
La classe [[P (complexité)|'''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érence nécessaire|date=1 novembre 2017}}.

=== P/poly contient des langages indécidables ===
Remarquons qu'il n'est pas nécessaire que le circuit correspondant à une entrée de taille <math>n</math> 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 <math>L</math> un langage indécidable sur l'alphabet <math>\{0,1\}</math>, et <math>U</math> le langage des mots <math>1^n</math> (autrement dit, <math>n</math> écrit en unaire) tels que <math>n</math>, écrit en binaire, est dans <math>L</math>. Il est clair que <math>U</math> est indécidable, pourtant il a des circuits polynomiaux : si <math>n</math> est dans <math>L</math>, alors <math>\mathcal{C}_n</math> est la conjonction des <math>n</math> bits d'entrée ; sinon <math>\mathcal{C}_n</math> est juste le booléen faux.

=== Théorème d'Adleman ===

Le théorème d'Adleman, démontré par [[Leonard Adleman]] {{Référence Harvard |Adleman  |1978}}, énonce que '''[[BPP_(complexité)|BPP]]''' est inclus dans '''P/poly'''<ref>{{Complexité algorithmique (Perifel)|numéro chapitre=625|titre chapitre=Circuits et algorithmes probabilistes|passage=163}}</ref>.

=== 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_(complexité)|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]] {{Référence Harvard |Karp|Lipton |1980}}), et de plus, on a '''[[Protocole d'Arthur et Merlin|AM]] '''= '''[[Protocole d'Arthur et Merlin|MA]]'''.
* Si '''NP''' n'est pas inclus dans '''P/poly''', comme P l'est, on en déduit que [[Problème P = NP|'''P''' est différent de '''NP''']].
* Si '''[[PSPACE]]''' est inclus dans '''P/poly''', alors '''PSPACE''' <math>=\Sigma_2^{\rm P}</math>, et on a même '''PSPACE''' = ''' MA'''
* Si '''[[EXPSPACE]]''' est inclus dans '''P/poly''', alors '''EXPSPACE''' <math>=\Sigma_2^{\rm P}</math> (c'est le [[théorème de Meyer]]), et on a même '''EXPSPACE''' = '''MA'''.

== Caractérisation ==
Il y a équivalence<ref name=":0">{{Chapitre|langue=en|prénom1=Ronald V.|nom1=Book|titre chapitre=On Sets with Small Information Content|titre ouvrage=Kolmogorov Complexity and Computational Complexity|éditeur=Springer Berlin Heidelberg|collection=EATCS Monographs on Theoretical Computer Science|date=1992|isbn=9783642777356|doi=10.1007/978-3-642-77735-6_3|lire en ligne=https://doi.org/10.1007/978-3-642-77735-6_3|consulté le=2019-07-15|passage=23–42}}</ref> entre :

# Un langage A est dans '''P/poly''' 
# il existe un [[langage creux]] S tel que A est réductible au sens de Turing en temps polynomial à S,
# 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 <ref>{{Article |prénom1=L. |nom1=Berman |prénom2=J. |nom2=Hartmanis |titre=On Isomorphisms and Density of $NP$ and Other Complete Sets |périodique=SIAM Journal on Computing |volume=6 |numéro=2 |date=1977-06-01 |issn=0097-5397 |doi=10.1137/0206023 |lire en ligne=https://epubs.siam.org/doi/10.1137/0206023 |consulté le=2019-07-15 |pages=305–322 }}</ref> (comme indiqué dans <ref name=":0" />) et l'équivalence entre 2 et 3 est montré dans <ref>{{Ouvrage |langue=en-gb |prénom1=José Luis |nom1=Balcázar |prénom2=Josep |nom2=Díaz |prénom3=Joaquim |nom3=Gabarró |titre=Structural Complexity I |date=1988 |collection=EATCS Monographs on Theoretical Computer Science Series |doi=10.1007/978-3-642-97062-7 |lire en ligne=https://link.springer.com/book/10.1007/978-3-642-97062-7 |consulté le=2019-07-15 }}</ref>.

== Références ==
{{Références}}

== Bibliographie ==
*Jean Goubault-Larrecq, ''Classes de complexité randomisées'', {{lire en ligne|lien=http://www.lsv.ens-cachan.fr/~goubault/Complexite/pcp.pdf|langue=fr}}

*{{chapitre
 |langue = en
 | prénom1 = Leonard M.
 | nom1 = Adleman 
 | lien auteur1 = Leonard Adleman
 | titre chapitre = Two theorems on random polynomial time
 | doi = 10.1109/SFCS.1978.37
 | pages = 75–83
 | titre ouvrage = Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computer Science
 | année = 1978}}

*{{chapitre
 |langue = en
 | prénom1 = Richard M.
 | nom1 = Karp
 | prénom2 = Richard J.
 | nom2 = Lipton
 | lien auteur1 = Richard Karp
 | titre chapitre = Some Connections between Nonuniform and Uniform Complexity Classes
 | pages = 302-309
 | titre ouvrage = Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA
 | année = 1980}}

== Lien externe ==
{{Traduction/Référence|en|P/poly|535494430|type=note}}
{{Complexity Zoo|fin=P#ppoly|nom=P/poly}}


{{Palette|Théorie de la complexité}}
{{Portail|informatique théorique}}

[[Catégorie:Classe de complexité]]