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é

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 Σ2 ∩ Π2

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[2]. Péter Gács a lui montré que BPP était en fait incluse dans Σ 2 P ∩ Π 2 P {\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].

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 Σ 2 P {\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.

Améliorations

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

Bibliographie

(en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, (ISBN 0-521-42426-7), chap. 7.5.2 (« BPP is in PH »)

Liens externes

  • (en) La classe BPP sur le Complexity Zoo
  • (en) La classe PH sur le Complexity Zoo

Notes et références

  1. ↑ (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, (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,‎ , p. 330–335
  3. ↑ (en) Clemens Lauteman, « BPP and the polynomial hierarchy », Inf. Proc. Lett., vol. 17, no 4,‎ , p. 215–217
  4. ↑ a et b (en) Dexter C. Kozen, Theory of Computation, Londres, Springer-Verlag, coll. « Texts in Computer Science », , 418 p. (ISBN 978-1-84628-297-3, lire en ligne)
  5. ↑ Ran Canetti, « More on BPP and the polynomial-time hierarchy », Elsevier, vol. 57, no 5,‎ , p. 237–241 (DOI 10.1016/0020-0190(96)00016-6)
  6. ↑ Alexander Russell et Ravi Sundaram, « Symmetric alternation captures BPP », Computational Complexity, vol. 7, no 2,‎ , p. 152–162 (ISSN 1016-3328, DOI 10.1007/s000370050007)
v · m
Théorie de la complexité (informatique théorique)
Classes de complexité
(liste)
Classes classiques
Classes randomisées et quantiques
Autres
Classes de fonctions calculables
Hiérarchies
Familles de classes
Théorèmes et outils
Théorèmes structurels
Outils et réductions
Approches non-standard
  • icône décorative Portail de l'informatique théorique