Théorème de Sipser-Gács-Lautemann

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le théorème de Sipser-Gács-Lautemann (ou théorème de Sipser-Lautemann ou de Sipser-Gács) est un théorème de la théorie de la complexité, un domaine de l'informatique théorique. Il donne une relation surprenante entre la classe probabiliste BPP et la hiérarchie polynomiale (qui n'a rien de probabiliste)[1].

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

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 Σ2 ∩ Π2. Et enfin Clemens Lautemann a donné une preuve plus simple de ce dernier résultat[3].

Preuve[modifier | modifier le code]

Améliorations[modifier | modifier le code]

On a en fait des inclusions plus fortes avec des classes intermédiaire : \mathsf{BPP} \subseteq \mathsf{MA} \subseteq \mathsf{S}_2^P \subseteq \Sigma_2 \cap \Pi_2

où MA est 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]

  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, no 4,‎ 1983, p. 215–217