Théorème de Sipser-Gács-Lautemann
De Wikipedia, l'encyclopédie encyclopedia
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.