Teorema de Sipser-Lautemann

Teorema de Sipser–Lautemann Na teoria da complexidade computacional, o teorema de Sipser–Lautemann ou teorema de Sipser–Gács–Lautemann afirma que o polinômio probabilístico de erro limitado (BPP) o tempo está contido na hierarquia de tempo polinomial, e mais especificamente Σ2 ∩ Π2.

Dentro 1983, Michael Sipser mostrou que o BPP está contido na hierarquia de tempo polinomial.[1] Péter Gács mostrou que o BPP está realmente contido em Σ2 ∩ Π2. Clemens Lautemann contribuiu dando uma prova simples da adesão do BPP em Σ2 ∩ Π2, também em 1983.[2] Conjectura-se que de fato BPP=P, que é uma afirmação muito mais forte do que o teorema de Sipser-Lautemann.

Conteúdo 1 Prova 1.1 Lema 1 1.2 Lema 2 1.3 Conclusão 2 Versão mais forte 3 References Proof Here we present the Lautemann's proof.[2] Sem perda de generalidade, uma máquina M ∈ BPP com erro ≤ 2−|x| pode ser escolhido. (Todos os problemas de BPP podem ser amplificados para reduzir exponencialmente a probabilidade de erro.) A ideia básica da prova é definir uma sentença Σ2 que seja equivalente a afirmar que x está na linguagem, eu, definido por M usando um conjunto de transformações das entradas de variáveis ​​aleatórias.

Como a saída de M depende da entrada aleatória, assim como a entrada x, é útil definir quais strings aleatórias produzem a saída correta como A(x) = {r | M(x,r) aceita}. A chave para a prova é notar que quando x ∈ L, UMA(x) é muito grande e quando x ∉ L, UMA(x) é muito pequeno. Usando paridade bit a bit, ⊕, um conjunto de transformações pode ser definido como A(x) ⊕t={r ⊕ t | r ∈ A(x)}. O primeiro lema principal da prova mostra que a união de um pequeno número finito dessas transformadas conterá todo o espaço de strings de entrada aleatórias. Usando este fato, uma sentença Σ2 e uma sentença Π2 podem ser geradas que são verdadeiras se e somente se x ∈ L (ver conclusão).

Lema 1 A ideia geral do lema um é provar que se A(x) cobre uma grande parte do espaço aleatório {estilo de exibição R={1,0}^{|r|}} então existe um pequeno conjunto de traduções que cobrirá todo o espaço aleatório. Em linguagem mais matemática: Se {estilo de exibição {fratura {|UMA(x)|}{|R|}}geq 1-{fratura {1}{2^{|x|}}}} , então {estilo de exibição existe t_{1},t_{2},ldots ,t_{|r|}} , Onde {estilo de exibição t_{eu}dentro {1,0}^{|r|}} de tal modo que {displaystyle bigcup _{eu}UMA(x)mais t_{eu}=R.} Prova. Escolha aleatoriamente t1, t2, ..., t|r|. Deixar {estilo de exibição S = bigcup _{eu}UMA(x)mais t_{eu}} (a união de todas as transformadas de A(x)).

Então, para todo r em R, {Pr estilo de exibição[rnotin S]= Pr[rnotin A(x)mais t_{1}]cdot Pr[rnotin A(x)mais t_{2}]cdots Pr[rnotin A(x)mais t_{|r|}]leq {fratura {1}{2^{|x|cdot |r|}}}.} A probabilidade de existir pelo menos um elemento em R não em S é {Pr estilo de exibição {Grande [}bigvee_{eu}(r_{eu}Notin S){Maior ]}soma leq _{eu}{fratura {1}{2^{|x|cdot |r|}}}={fratura {2^{|r|}}{2^{|x|cdot |r|}}}<1.} Therefore {displaystyle Pr[S=R]geq 1-{frac {2^{|r|}}{2^{|x|cdot |r|}}}>0.} Assim, há uma seleção para cada {estilo de exibição t_{1},t_{2},ldots ,t_{|r|}} de tal modo que {displaystyle bigcup _{eu}UMA(x)mais t_{eu}=R.} Lema 2 O lema anterior mostra que A(x) pode cobrir todos os pontos possíveis no espaço usando um pequeno conjunto de traduções. Complementar a este, para x ∉ L apenas uma pequena fração do espaço é coberta por {estilo de exibição S = bigcup _{eu}UMA(x)mais t_{eu}} . Nós temos: {estilo de exibição {fratura {|S|}{|R|}}leq |r|cdot {fratura {|UMA(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

Se você quiser conhecer outros artigos semelhantes a Teorema de Sipser-Lautemann você pode visitar a categoria Randomized algorithms.

Deixe uma resposta

seu endereço de e-mail não será publicado.

Ir para cima

Usamos cookies próprios e de terceiros para melhorar a experiência do usuário Mais informação