BPP (complexité)

En théorie de la complexité computationnelle , une branche de l'informatique, le temps polynomial probabiliste à erreur bornée ( BPP ) est la classe de problèmes de décision résolubles par une machine de Turing probabiliste en temps polynomial avec une probabilité d'erreur bornée à 1/3 pour toutes les instances. Le BPP est l'une des plus grandes classes pratiques de problèmes, ce qui signifie que la plupart des problèmes d'intérêt dans le BPP ont des algorithmes probabilistes efficaces qui peuvent être exécutés rapidement sur de vraies machines modernes. Le BPP contient également P , la classe de problèmes résolubles en temps polynomial avec une machine déterministe, car une machine déterministe est un cas particulier de machine probabiliste.

De manière informelle, un problème est en BPP s'il existe un algorithme pour celui-ci qui possède les propriétés suivantes :

• Il est permis de lancer des pièces et de prendre des décisions aléatoires
• Il est garanti de fonctionner en temps polynomial
• À chaque exécution de l'algorithme, la probabilité de donner une mauvaise réponse est au plus de 1/3, que la réponse soit OUI ou NON.

Un langage L est en BPP si et seulement s'il existe une machine de Turing probabiliste M , telle que

• M s'exécute pendant un temps polynomial sur toutes les entrées
• Pour tout x dans L , M génère 1 avec une probabilité supérieure ou égale à 2/3
• Pour tout x non compris dans L , M renvoie 1 avec une probabilité inférieure ou égale à 1/3

Contrairement à la classe de complexité ZPP , la machine M doit fonctionner pendant un temps polynomial sur toutes les entrées, quel que soit le résultat des lancers aléatoires de pièces.

Alternativement, BPP peut être défini en utilisant uniquement des machines de Turing déterministes. Un langage L est en BPP si et seulement s'il existe un polynôme p et une machine de Turing déterministe M , tels que

• M s'exécute pendant un temps polynomial sur toutes les entrées
• Pour tout x dans L , la fraction de chaînes y de longueur p (| x |) qui satisfont ⁠ ⁠ est supérieure ou égale à 2/3
• Pour tout x non compris dans L , la fraction de chaînes y de longueur p (| x |) qui satisfont ⁠ ⁠ est inférieure ou égale à 1/3

Dans cette définition, la chaîne y correspond à la sortie des lancers aléatoires de pièces que la machine de Turing probabiliste aurait effectués. Pour certaines applications, cette définition est préférable car elle ne mentionne pas les machines de Turing probabilistes.

En pratique, une probabilité d'erreur de 1/3 pourrait ne pas être acceptable ; cependant, le choix de 1/3 dans la définition est arbitraire. Modifier la définition pour utiliser une constante entre 0 et 1/2 (exclusif) à la place de 1/3 ne modifierait pas l'ensemble résultant BPP . Par exemple, si l'on définissait la classe avec la restriction que l'algorithme peut se tromper avec une probabilité au plus égale à 1/2 ¹⁰⁰ , cela donnerait la même classe de problèmes. La probabilité d'erreur n'a même pas besoin d'être constante : la même classe de problèmes est définie en autorisant une erreur aussi élevée que 1/2 − n ^{− c} d'une part, ou en exigeant une erreur aussi petite que 2 ^{− n c} d'autre part, où c est une constante positive et n est la longueur de l'entrée. Cette flexibilité dans le choix de la probabilité d'erreur est basée sur l'idée d'exécuter un algorithme sujet aux erreurs plusieurs fois et d'utiliser le résultat majoritaire des exécutions pour obtenir un algorithme plus précis. La probabilité que la majorité des exécutions soient erronées diminue de manière exponentielle en raison de la limite de Chernoff .

Tous les problèmes de P sont évidemment aussi de BPP . Cependant, de nombreux problèmes sont connus pour être de BPP mais pas de P. Le nombre de ces problèmes diminue et on suppose que P = BPP .

Pendant longtemps, l'un des problèmes les plus connus connus pour être dans BPP mais pas connus pour être dans P était le problème de déterminer si un nombre donné est premier . Cependant, dans l'article de 2002 PRIMES is in P , Manindra Agrawal et ses étudiants Neeraj Kayal et Nitin Saxena ont trouvé un algorithme déterministe en temps polynomial pour ce problème, montrant ainsi qu'il est dans P .

Un exemple important de problème dans BPP (en fait dans co-RP ) qui n'est pas encore connu dans P est le test d'identité polynomiale , le problème de déterminer si un polynôme est identiquement égal au polynôme nul, lorsque vous avez accès à la valeur du polynôme pour une entrée donnée, mais pas aux coefficients. En d'autres termes, existe-t-il une affectation de valeurs aux variables telle que lorsqu'un polynôme non nul est évalué sur ces valeurs, le résultat soit non nul ? Il suffit de choisir la valeur de chaque variable uniformément au hasard dans un sous-ensemble fini d'au moins d valeurs pour obtenir une probabilité d'erreur bornée, où d est le degré total du polynôme.

Si l'on supprime l'accès au hasard de la définition de BPP , on obtient la classe de complexité P. Dans la définition de la classe, si l'on remplace la machine de Turing ordinaire par un ordinateur quantique , on obtient la classe BQP .

L'ajout d'une postsélection à BPP , ou l'autorisation d'avoir des chemins de calcul de longueurs différentes, donne la classe BPP _path . BPP _path est connu pour contenir NP , et il est contenu dans son homologue quantique PostBQP .

Un algorithme de Monte Carlo est un algorithme randomisé qui a de fortes chances d'être correct. Les problèmes de la classe BPP ont des algorithmes de Monte Carlo avec un temps d'exécution polynomial limité. Cela est comparé à un algorithme de Las Vegas qui est un algorithme randomisé qui génère soit la bonne réponse, soit un échec avec une faible probabilité. Les algorithmes de Las Vegas avec des temps d'exécution polynomiaux limités sont utilisés pour définir la classe ZPP . Alternativement, ZPP contient des algorithmes probabilistes qui sont toujours corrects et ont un temps d'exécution polynomial attendu. Cela est plus faible que de dire qu'il s'agit d'un algorithme en temps polynomial, car il peut s'exécuter pendant un temps super-polynomial, mais avec une probabilité très faible.

Il est connu que BPP est fermé en complément ; c'est-à-dire que BPP = co-BPP . BPP est faible pour lui-même, ce qui signifie qu'une machine BPP avec la puissance de résoudre instantanément les problèmes BPP (une machine oracle BPP ) n'est pas plus puissante que la machine sans cette puissance supplémentaire. En symboles, BPP ^BPP = BPP .

La relation entre BPP et NP est inconnue : on ne sait pas si BPP est un sous-ensemble de NP , si NP est un sous-ensemble de BPP ou si aucun des deux n'est contenu dans BPP. Si NP est contenu dans BPP , ce qui est considéré comme peu probable car cela impliquerait des solutions pratiques pour les problèmes NP-complets , alors NP = RP et PH ⊆ BPP .

On sait que RP est un sous-ensemble de BPP et que BPP est un sous-ensemble de PP . On ne sait pas si ces deux sont des sous-ensembles stricts, car on ne sait même pas si P est un sous-ensemble strict de PSPACE . BPP est contenu dans le deuxième niveau de la hiérarchie polynomiale et il est donc contenu dans PH . Plus précisément, le théorème de Sipser-Lautemann stipule que . En conséquence, P = NP conduit à P = BPP puisque PH se réduit à P dans ce cas. Ainsi, soit P = BPP , soit P ≠ NP , soit les deux.

Le théorème d'Adleman stipule que l'appartenance à tout langage dans BPP peut être déterminée par une famille de circuits booléens de taille polynomiale , ce qui signifie que BPP est contenu dans P/poly . En effet, en conséquence de la preuve de ce fait, tout algorithme BPP opérant sur des entrées de longueur limitée peut être dérandomisé en un algorithme déterministe utilisant une chaîne fixe de bits aléatoires. Trouver cette chaîne peut cependant être coûteux. Certains résultats de séparation faible pour les classes de temps de Monte Carlo ont été prouvés par Karpinski & Verbeek (1987a), voir aussi Karpinski & Verbeek (1987b).

La classe BPP est fermée sous complémentation, union et intersection.

Par rapport aux oracles, nous savons qu'il existe des oracles A et B, tels que P ^A = BPP ^A et P ^B ≠ BPP ^B . De plus, par rapport à un oracle aléatoire de probabilité 1, P = BPP et BPP est strictement contenu dans NP et co-NP .

Il existe même un oracle dans lequel ⁠ ⁠ (et donc ⁠ ⁠ ), qui peut être construit de manière itérative comme suit. Pour un problème complet E ^NP (relativisé) fixe, l'oracle donnera des réponses correctes avec une probabilité élevée s'il est interrogé avec l'instance du problème suivie d'une chaîne aléatoire de longueur kn ( n est la longueur de l'instance ; k est une petite constante appropriée). Commencez avec n = 1. Pour chaque instance du problème de longueur n, fixez les réponses de l'oracle (voir lemme ci-dessous) pour fixer la sortie de l'instance. Ensuite, fournissez les sorties d'instance pour les requêtes constituées de l'instance suivie d' une chaîne de longueur kn , puis traitez la sortie pour les requêtes de longueur ≤( k +1) n comme fixe, et continuez avec les instances de longueur n +1.

Le lemme garantit que (pour un k suffisamment grand ), il est possible de faire la construction tout en laissant suffisamment de chaînes pour les réponses E ^NP relativisées . De plus, nous pouvons garantir que pour le E ^NP relativisé , le temps linéaire suffit, même pour les problèmes de fonction (si l'on dispose d'un oracle de fonction et d'une taille de sortie linéaire) et avec une probabilité d'erreur exponentiellement faible (avec un exposant linéaire). De plus, cette construction est efficace dans la mesure où, étant donné un oracle arbitraire A, nous pouvons arranger l'oracle B pour avoir P ^A ≤ P ^B et EXP ^{NP A} = EXP ^{NP B} = BPP ^B . De plus, pour un oracle ZPP =EXP (et donc ZPP=BPP=EXP<NEXP ), on fixerait les réponses dans le calcul E relativisé à une non-réponse spéciale, garantissant ainsi qu'aucune fausse réponse ne soit donnée.

La plupart des experts du domaine supposent l'existence de certains générateurs de nombres pseudo-aléatoires puissants. De tels générateurs pourraient remplacer les vrais nombres aléatoires dans tout algorithme randomisé en temps polynomial, produisant des résultats indiscernables. La conjecture selon laquelle ces générateurs existent implique que le caractère aléatoire ne confère pas de puissance de calcul supplémentaire au calcul en temps polynomial, c'est-à-dire que P = RP = BPP . Plus fortement , l'hypothèse selon laquelle P = BPP est dans un certain sens équivalente à l'existence de générateurs de nombres pseudo-aléatoires puissants.

László Babai , Lance Fortnow , Noam Nisan et Avi Wigderson ont montré qu'à moins que EXPTIME ne se réduise à MA , BPP est contenu dans

$0\}\{\; extsf\; \{i.o.-DTIME\}\}\backslash left(2^\{n^\{\backslash varepsilon\; \}\}\; ight).\text{io-SUBEXP}={\bigcap }_{\epsilon >0}\text{io-DTIME}\left(2^{n^{\epsilon }}\right).$0}{ extsf {io-DTIME}}\gauche(2^{n^{\varepsilon }}\droite).}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f52790872474726ec0b3d32fcbe760d5bfcfafac">

La classe io-SUBEXP , qui signifie infiniment souvent SUBEXP , contient des problèmes qui ont des algorithmes à temps sous-exponentiel pour un nombre infini de tailles d'entrée. Ils ont également montré que P = BPP si la hiérarchie à temps exponentiel, qui est définie en termes de hiérarchie polynomiale et E comme E ^PH , s'effondre à E ; cependant, notez que la hiérarchie à temps exponentiel est généralement supposée ne pas s'effondrer.

Russell Impagliazzo et Avi Wigderson ont montré que si un problème dans E , où

a une complexité de circuit de 2 ^{Ω( n )} alors P = BPP .