Teorema di Sipser-Lautemann

Teorema di Sipser-Lautemann Nella teoria della complessità computazionale, il teorema di Sipser-Lautemann o il teorema di Sipser-Gács-Lautemann afferma che il polinomio probabilistico a errore limitato (BPP) il tempo è contenuto nella gerarchia del tempo polinomiale, e più precisamente Σ2 ∩ Π2.

In 1983, Michael Sipser ha mostrato che BPP è contenuto nella gerarchia del tempo polinomiale.[1] Péter Gács ha mostrato che BPP è effettivamente contenuto in Σ2 ∩ Π2. Clemens Lautemann ha contribuito dando una semplice prova dell'appartenenza di BPP a Σ2 ∩ Π2, anche in 1983.[2] Si congettura infatti che BPP=P, che è un'affermazione molto più forte del teorema di Sipser-Lautemann.

Contenuti 1 Prova 1.1 Lemma 1 1.2 Lemma 2 1.3 Conclusione 2 Versione più forte 3 References Proof Here we present the Lautemann's proof.[2] Senza perdita di generalità, una macchina M ∈ BPP con errore ≤ 2−|X| può essere scelto. (Tutti i problemi BPP possono essere amplificati per ridurre esponenzialmente la probabilità di errore.) L'idea di base della dimostrazione è quella di definire una frase Σ2 che equivale ad affermare che x è nel linguaggio, l, definito da M utilizzando un insieme di trasformazioni degli input di variabili casuali.

Poiché l'output di M dipende dall'input casuale, così come l'input x, è utile definire quali stringhe casuali producono l'output corretto come A(X) = {r | M(X,r) accetta}. La chiave della dimostrazione è notare che quando x ∈ L, UN(X) è molto grande e quando x ∉ L, UN(X) è molto piccolo. Usando la parità bit per bit, ⊕, un insieme di trasformazioni può essere definito come A(X) ⊕ t={r ⊕ t | r ∈ A(X)}. Il primo lemma principale della dimostrazione mostra che l'unione di un piccolo numero finito di queste trasformazioni conterrà l'intero spazio delle stringhe di input casuali. Usando questo fatto, si possono generare una frase Σ2 e una frase Π2 che è vera se e solo se x ∈ L (vedi conclusione).

Lemma 1 L'idea generale del lemma uno è dimostrare che se A(X) copre gran parte dello spazio casuale {stile di visualizzazione R={1,0}^{|r|}} allora esiste un piccolo insieme di traduzioni che coprirà l'intero spazio casuale. In un linguaggio più matematico: Se {stile di visualizzazione {frac {|UN(X)|}{|R|}}geq 1-{frac {1}{2^{|X|}}}} , poi {lo stile di visualizzazione esiste t_{1},t_{2},ldot ,t_{|r|}} , dove {stile di visualizzazione t_{io}in {1,0}^{|r|}} tale che {displaystyle tazza grande _{io}UN(X)oplus t_{io}=R.} Prova. Scegli casualmente t1, t2, ..., t|r|. Permettere {displaystyle S=tazza grande _{io}UN(X)oplus t_{io}} (l'unione di tutte le trasformate di A(X)).

Così, per tutti r in R, {stile di visualizzazione 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|}}}.} La probabilità che esista almeno un elemento in R non in S è {stile di visualizzazione Pr {Grande [}bigvee _{io}(r_{io}notin S){Più grande ]}leq somma _{io}{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.} Quindi c'è una selezione per ciascuno {stile di visualizzazione t_{1},t_{2},ldot ,t_{|r|}} tale che {displaystyle tazza grande _{io}UN(X)oplus t_{io}=R.} Lemma 2 Il lemma precedente mostra che A(X) può coprire ogni possibile punto dello spazio utilizzando un piccolo insieme di traduzioni. Complementare a questo, per x ∉ L è coperta solo una piccola frazione dello spazio {displaystyle S=tazza grande _{io}UN(X)oplus t_{io}} . abbiamo: {stile di visualizzazione {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