Théorème de Sipser-Gács-Lautemann

La classe BPP contient exactement les problèmes qui sont "presque" décidés par une machine de Turing probabiliste en temps polynomial dans le sens suivant : la machine se trompe avec une probabilité inférieure à 1/3. La classe Σ₂ contient les problèmes décidés par une machine de Turing déterministe en temps polynomial qui fait appel à un oracle NP.

Michael Sipser a montré en 1983 que BPP était incluse dans la hiérarchie polynomiale[2]. Péter Gács a lui montré que BPP était en fait incluse dans ${\displaystyle \Sigma _{2}^{P}\cap \Pi _{2}^{P}}$. Et enfin Clemens Lautemann a donné une preuve plus simple de ce dernier résultat[3].

Dans cette section, nous donnons la démonstration en suivant le chapitre correspondant dans le livre Theory of Computation de Kozen[4]. Comme BPP est clos par complémentaire, il suffit de montrer que BPP est incluse dans ${\displaystyle \Sigma _{2}^{P}}$. Par le lemme d'amplification[4], on démontre qu'en répétant l'exécution d'une machine M, on peut diminuer de façon exponentielle la probabilité que d'erreur. On se ramène ensuite à l'existence d'un certificat qui garantit la correction d'un certain oracle.

On a en fait des inclusions plus fortes avec des classes intermédiaires : ${\displaystyle {\mathsf {BPP}}\subseteq {\mathsf {MA}}\subseteq {\mathsf {S}}_{2}^{P}\subseteq \Sigma _{2}^{P}\cap \Pi _{2}^{P}}$[5] - [6]

où MA est une classe de complexité basée sur un protocole d'Arthur et Merlin et ${\displaystyle {\mathsf {S}}_{2}^{P}}$ est la classe de base de la hiérarchie symétrique.

(en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 7.5.2 (« BPP is in PH »)

• (en) La classe BPP sur le Complexity Zoo
• (en) La classe PH sur le Complexity Zoo