P/poly
- Article
- Discussion
Outils
Général
Imprimer / exporter
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 NP ⊈ P/poly, alors on résout le problème ouvert P est différent de NP[2].
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].
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 :
On dit d'un langage satisfaisant cette propriété qu'il a des circuits polynomiaux.
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.
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].
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.
Le théorème d'Adleman, démontré par Leonard Adleman (Adleman 1978), énonce que BPP est inclus dans P/poly[5].
P/poly a une place importante en théorie de la complexité : plusieurs propriétés importantes s'expriment à l'aide de P/poly :
Il y a équivalence[6] entre :
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].
(en) La classe P/poly sur le Complexity Zoo
Classes de complexité (liste) |
| ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Théorèmes et outils |
| ||||||||||||
Approches non-standard |