Sipser–Lautemann theorem

Sipser-Lautemann-Theorem In der Berechnungskomplexitätstheorie, Das Sipser-Lautemann-Theorem oder das Sipser-Gács-Lautemann-Theorem besagt, dass das probabilistische Polynom mit begrenztem Fehler (BPP) Die Zeit ist in der polynomiellen Zeithierarchie enthalten, und genauer Σ2 ∩ Π2.

Im 1983, Michael Sipser zeigte, dass BPP in der polynomiellen Zeithierarchie enthalten ist.[1] Péter Gács zeigte, dass BPP tatsächlich in Σ2 ∩ Π2 enthalten ist. Clemens Lautemann trug dazu bei, indem er einen einfachen Beweis für die Mitgliedschaft von BPP in Σ2 ∩ Π2 lieferte, auch in 1983.[2] Es wird vermutet, dass tatsächlich BPP=P ist, Dies ist eine viel stärkere Aussage als das Sipser-Lautemann-Theorem.

Inhalt 1 Nachweisen 1.1 Lemma 1 1.2 Lemma 2 1.3 Fazit 2 Stärkere Version 3 References Proof Here we present the Lautemann's proof.[2] Ohne Verlust der Allgemeinheit, eine Maschine M ∈ BPP mit Fehler ≤ 2−|x| kann gewählt werden. (Alle BPP-Probleme können verstärkt werden, um die Fehlerwahrscheinlichkeit exponentiell zu reduzieren.) Die Grundidee des Beweises besteht darin, einen Σ2-Satz zu definieren, der der Aussage entspricht, dass x in der Sprache vorkommt, L, definiert durch M unter Verwendung eines Satzes von Transformationen der zufälligen Variableneingaben.

Da die Ausgabe von M von einer zufälligen Eingabe abhängt, sowie die Eingabe x, Es ist nützlich zu definieren, welche zufälligen Zeichenfolgen die korrekte Ausgabe als A erzeugen(x) = {r | M(x,r) akzeptiert}. Der Schlüssel zum Beweis ist, dass für x ∈ L, EIN(x) sehr groß ist und wenn x ∉ L, EIN(x) ist sehr klein. Durch die Verwendung von bitweiser Parität, ⊕, ein Satz von Transformationen kann als A definiert werden(x) ⊕ t={r ⊕ t | r ∈ A(x)}. Das erste Hauptlemma des Beweises zeigt, dass die Vereinigung einer kleinen endlichen Anzahl dieser Transformationen den gesamten Raum zufälliger Eingabezeichenfolgen enthalten wird. Diese Tatsache nutzen, ein Σ2-Satz und ein Π2-Satz können erzeugt werden, der genau dann wahr ist, wenn x ∈ L (siehe Fazit).

Lemma 1 Die allgemeine Idee von Lemma eins besteht darin, zu beweisen, dass, wenn A(x) deckt einen großen Teil des zufälligen Raums ab {Anzeigestil R={1,0}^{|r|}} dann gibt es einen kleinen Satz von Übersetzungen, der den gesamten zufälligen Raum abdeckt. In mathematischer Sprache: Wenn {Anzeigestil {frac {|EIN(x)|}{|R|}}geq 1-{frac {1}{2^{|x|}}}} , dann {Anzeigestil existiert t_{1},t_{2},Punkte ,t_{|r|}} , wo {Anzeigestil t_{ich}in {1,0}^{|r|}} so dass {displaystyle bigcup _{ich}EIN(x)oplus t_{ich}=R.} Nachweisen. Wähle zufällig t1, t2, ..., t|r|. Lassen {Anzeigestil S=bigcup _{ich}EIN(x)oplus t_{ich}} (die Vereinigung aller Transformierten von A(x)).

So, für alle r in R, {Anzeigestil Pr[rnotin S]= Pr[rnotin A(x)oplus t_{1}]cdot Pr[rnotin A(x)oplus t_{2}]cdots Pr[rnotin A(x)oplus t_{|r|}]leq {frac {1}{2^{|x|cdot |r|}}}.} Die Wahrscheinlichkeit, dass mindestens ein Element in R und nicht in S existiert, ist {Anzeigestil Pr {Groß [}bigvee _{ich}(r_{ich}Notin S){Größer ]}Leq-Summe _{ich}{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.} Somit gibt es für jeden eine Auswahl {Anzeigestil t_{1},t_{2},Punkte ,t_{|r|}} so dass {displaystyle bigcup _{ich}EIN(x)oplus t_{ich}=R.} Lemma 2 Das vorige Lemma zeigt, dass A(x) kann mit einer kleinen Menge von Übersetzungen jeden möglichen Punkt im Raum abdecken. Ergänzend hierzu, für x ∉ L wird nur ein kleiner Bruchteil des Raumes abgedeckt {Anzeigestil S=bigcup _{ich}EIN(x)oplus t_{ich}} . Wir haben: {Anzeigestil {frac {|S|}{|R|}}leq |r|cdot {frac {|EIN(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