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 surprenante^{[Selon qui ?]} car la définition de la hiérarchie polynomiale ne fait pas référence à la théorie des probabilités.

Énoncé[modifier | modifier le code]

Théorème de Sipser–Gács–Lautemann — La classe de complexité BPP est incluse dans la hiérarchie polynomiale (PH) plus précisément dans Σ₂ ∩ Π₂

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.

Histoire[modifier | modifier le code]

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 $\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].

Idée de la démonstration[modifier | modifier le code]

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 $\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.

Améliorations[modifier | modifier le code]

On a en fait des inclusions plus fortes avec des classes intermédiaires : ${\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 ${\mathsf {S}}_{2}^{P}$ est la classe de base de la hiérarchie symétrique.

Bibliographie[modifier | modifier le code]

(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 »)

Liens externes[modifier | modifier le code]

Notes et références[modifier | modifier le code]

↑ (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) Michael Sipser, « A complexity theoretic approach to randomness », In Proceedings of the 15th ACM Symposium on Theory of Computing,‎ 1983, p. 330–335
↑ (en) Clemens Lauteman, « BPP and the polynomial hierarchy », Inf. Proc. Lett., vol. 17, n^o 4,‎ 1983, p. 215–217
↑ ^{a et b} (en) Dexter C. Kozen, Theory of Computation, Londres, Springer-Verlag, coll. « Texts in Computer Science », 2006, 418 p. (ISBN 978-1-84628-297-3, lire en ligne)
↑ Ran Canetti, « More on BPP and the polynomial-time hierarchy », Elsevier, vol. 57, n^o 5,‎ 1996, p. 237–241 (DOI 10.1016/0020-0190(96)00016-6)
↑ Alexander Russell et Ravi Sundaram, « Symmetric alternation captures BPP », Computational Complexity, vol. 7, n^o 2,‎ 1998, p. 152–162 (ISSN 1016-3328, DOI 10.1007/s000370050007)

Portail de l'informatique théorique

[1] (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 »)

[2] (en) Michael Sipser, « A complexity theoretic approach to randomness », In Proceedings of the 15th ACM Symposium on Theory of Computing,‎ 1983, p. 330–335

[3] (en) Clemens Lauteman, « BPP and the polynomial hierarchy », Inf. Proc. Lett., vol. 17, n^o 4,‎ 1983, p. 215–217

[:0-4] {a et b} (en) Dexter C. Kozen, Theory of Computation, Londres, Springer-Verlag, coll. « Texts in Computer Science », 2006, 418 p. (ISBN 978-1-84628-297-3, lire en ligne)

[canetti-5] Ran Canetti, « More on BPP and the polynomial-time hierarchy », Elsevier, vol. 57, n^o 5,‎ 1996, p. 237–241 (DOI 10.1016/0020-0190(96)00016-6)

[russell-sundaram-6] Alexander Russell et Ravi Sundaram, « Symmetric alternation captures BPP », Computational Complexity, vol. 7, n^o 2,‎ 1998, p. 152–162 (ISSN 1016-3328, DOI 10.1007/s000370050007)

[1]

[2]

[3]

[4]

[5]

[6]