Théorème de Sipser-Lautemann

Théorème de Sipser – Lautemann Dans la théorie de la complexité computationnelle, le théorème de Sipser – Lautemann ou le théorème de Sipser – Gács – Lautemann stipule que le polynôme probabiliste à erreur bornée (BPP) le temps est contenu dans la hiérarchie polynomiale du temps, et plus précisément Σ2 ∩ Π2.

Dans 1983, Michael Sipser a montré que BPP est contenu dans la hiérarchie temporelle polynomiale.[1] Péter Gács a montré que BPP est en fait contenu dans Σ2 ∩ Π2. Clemens Lautemann a contribué en donnant une preuve simple de l'appartenance de BPP à Σ2 ∩ Π2, aussi dans 1983.[2] On conjecture qu'en fait BPP=P, qui est une déclaration beaucoup plus forte que le théorème de Sipser-Lautemann.

Contenu 1 Preuve 1.1 Lemme 1 1.2 Lemme 2 1.3 Conclusion 2 Version plus forte 3 References Proof Here we present the Lautemann's proof.[2] Sans perte de généralité, une machine M ∈ BPP avec erreur ≤ 2−|X| peut être choisi. (Tous les problèmes BPP peuvent être amplifiés pour réduire la probabilité d'erreur de façon exponentielle.) L'idée de base de la preuve est de définir une phrase Σ2 qui équivaut à affirmer que x est dans le langage, L, défini par M en utilisant un ensemble de transformées des entrées variables aléatoires.

Puisque la sortie de M dépend de l'entrée aléatoire, ainsi que l'entrée x, il est utile de définir quelles chaînes aléatoires produisent la sortie correcte comme A(X) = {r | M(X,r) accepte}. La clé de la preuve est de noter que lorsque x ∈ L, UN(X) est très grand et quand x ∉ L, UN(X) est très petit. En utilisant la parité au niveau du bit, ⊕, un ensemble de transformées peut être défini comme A(X) ⊕ t={r ⊕ t | r ∈ A(X)}. Le premier lemme principal de la preuve montre que l'union d'un petit nombre fini de ces transformées contiendra tout l'espace des chaînes d'entrée aléatoires. Utilisant ce fait, une phrase Σ2 et une phrase Π2 peuvent être générées qui sont vraies si et seulement si x ∈ L (voir conclusion).

Lemme 1 L'idée générale du lemme 1 est de prouver que si A(X) couvre une grande partie de l'espace aléatoire {style d'affichage R={1,0}^{|r|}} alors il existe un petit ensemble de traductions qui couvrira tout l'espace aléatoire. En langage plus mathématique: Si {style d'affichage {frac {|UN(X)|}{|R|}}gq 1-{frac {1}{2^{|X|}}}} , alors {le style d'affichage existe t_{1},t_{2},ldots ,t_{|r|}} , où {style d'affichage t_{je}dans {1,0}^{|r|}} tel que {style d'affichage bigcup _{je}UN(X)plus t_{je}=R.} Preuve. Choisissez au hasard t1, t2, ..., t|r|. Laisser {style d'affichage S=grande tasse _{je}UN(X)plus t_{je}} (la réunion de toutes les transformées de A(X)).

Alors, pour tout r dans R, {style d'affichage Pr[rnotin S]=Pr[notin A(X)plus t_{1}]cdot Pr[notin A(X)plus t_{2}]cdotspr[notin A(X)plus t_{|r|}]leq {frac {1}{2^{|X|cdot |r|}}}.} La probabilité qu'il existe au moins un élément dans R pas dans S est {style d'affichage Pr {Gros [}gros _{je}(r_{je}notin S){Plus grand ]}leq somme _{je}{frac {1}{2^{|X|cdot |r|}}}={frac {2^{|r|}}{2^{|X|cdot |r|}}}<1.} Therefore {displaystyle Pr[S=R]geq 1-{frac {2^{|r|}}{2^{|x|cdot |r|}}}>0.} Il y a donc une sélection pour chaque {style d'affichage t_{1},t_{2},ldots ,t_{|r|}} tel que {style d'affichage bigcup _{je}UN(X)plus t_{je}=R.} Lemme 2 Le lemme précédent montre que A(X) peut couvrir tous les points possibles de l'espace en utilisant un petit ensemble de traductions. Complémentaire à cela, pour x ∉ L seule une petite fraction de l'espace est couverte par {style d'affichage S=grande tasse _{je}UN(X)plus t_{je}} . Nous avons: {style d'affichage {frac {|S|}{|R|}}leq |r|cdot {frac {|UN(X)|}{|R|}}leq |r|cdot 2^{-|X|}<1} because {displaystyle |r|} is polynomial in {displaystyle |x|} . Conclusion The lemmas show that language membership of a language in BPP can be expressed as a Σ2 expression, as follows. {displaystyle xin Liff exists t_{1},t_{2},dots ,t_{|r|},forall rin Rbigvee _{1leq ileq |r|}(M(x,roplus t_{i}){text{ accepts}}).} That is, x is in language L if and only if there exist {displaystyle |r|} binary vectors, where for all random bit vectors r, TM M accepts at least one random vector ⊕ ti. The above expression is in Σ2 in that it is first existentially then universally quantified. Therefore BPP ⊆ Σ2. Because BPP is closed under complement, this proves BPP ⊆ Σ2 ∩ Π2. Stronger version The theorem can be strengthened to {displaystyle {mathsf {BPP}}subseteq {mathsf {MA}}subseteq {mathsf {S}}_{2}^{P}subseteq Sigma _{2}cap Pi _{2}} (see MA, SP 2).[3][4] References ^ Sipser, Michael (1983). "A complexity theoretic approach to randomness". Proceedings of the 15th ACM Symposium on Theory of Computing. ACM Press: 330–335. CiteSeerX 10.1.1.472.8218. ^ Jump up to: a b Lautemann, Clemens (1983). "BPP and the polynomial hierarchy". Inf. Proc. Lett. 17. 17 (4): 215–217. doi:10.1016/0020-0190(83)90044-3. ^ Canetti, Ran (1996). "More on BPP and the polynomial-time hierarchy". Information Processing Letters. 57 (5): 237–241. doi:10.1016/0020-0190(96)00016-6. ^ Russell, Alexander; Sundaram, Ravi (1998). "Symmetric alternation captures BPP". Computational Complexity. 7 (2): 152–162. CiteSeerX 10.1.1.219.3028. doi:10.1007/s000370050007. ISSN 1016-3328. S2CID 15331219. Categories: Structural complexity theoryRandomized algorithmsTheorems in computational complexity theory