En informatique théorique, plus précisément en théorie de la complexité, le théorème de Sipser-Gács-Lautemann (ou théorème de Sipser-Lautemann ou de Sipser-Gács) est le théorème qui énonce que la classe probabiliste BPP (bounded-error probabilistic polynomial time) est incluse dans la hiérarchie polynomiale^[1]. Cette relation d'inclusion est surprenante^{[Selon qui ?]} car la définition de la hiérarchie polynomiale ne fait pas référence à la théorie des probabilités.

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}}$^{[réf. nécessaire]}. 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

• Portail de l'informatique théorique