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. Cette relation d'inclusion est surprenante car la définition de la hiérarchie polynomiale ne fait pas référence à la théorie des probabilités.
Énoncé
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 Σ2 contient les problèmes décidés par une machine de Turing déterministe en temps polynomial qui fait appel à un oracle NP.
Histoire
Michael Sipser a montré en 1983 que BPP était incluse dans la hiérarchie polynomiale. Péter Gács a lui montré que BPP était en fait incluse dans . Et enfin Clemens Lautemann a donné une preuve plus simple de ce dernier résultat.
Idée de la démonstration Dans cette section, nous donnons la démonstration en suivant le chapitre correspondant dans le livre Theory of Computation de Kozen. Comme BPP est clos par complémentaire, il suffit de montrer que BPP est incluse dans . Par le lemme d'amplification, 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.
Améliorations On a en fait des inclusions plus fortes avec des classes intermédiaires :
où MA est une classe de complexité basée sur un protocole d'Arthur et Merlin et est la classe de base de la hiérarchie symétrique.
Bibliographie
Liens externes
Notes et références
Sipser-Gács-Lautemann