Théorème de Sipser-Gács-Lautemann
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 surprenanteModèle:Selon qui car la définition de la hiérarchie polynomiale ne fait pas référence à la théorie des probabilités.
Énoncé
Modèle:ThéorèmeLa 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[2]. Péter Gács a lui montré que BPP était en fait incluse dans Modèle:Référence nécessaire. Et enfin Clemens Lautemann a donné une preuve plus simple de ce dernier résultat[3].
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[4]. Comme BPP est clos par complémentaire, il suffit de montrer que BPP est incluse dans . 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.
Améliorations
On a en fait des inclusions plus fortes avec des classes intermédiaires : [5]Modèle:,[6]
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
Modèle:Computational Complexity (Arora et Barak)