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. 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 P est différent de NP.
Définitions Il y a deux définitions équivalentes, la première donnée avec le modèle de calcul des circuits booléens, l'autre avec des machines de Turing.
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.
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 , énonce que BPP est inclus dans P/poly.
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 ), 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 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 (comme indiqué dans ) et l'équivalence entre 2 et 3 est montré dans .
Références
Bibliographie Jean Goubault-Larrecq, Classes de complexité randomisées,
Lien externe
Catégorie:Classe de complexité