# Teorema de Sipser–Lautemann

Em teoria da complexidade computacional, o teorema Sipser-Lautemann ou teorema Sipser-Gács-Lautemann estabelece que Bounded-error probabilistic polinomial time (BPP), está contida na hierarquia de tempo polinomial, e, mais especificamente, em Σ$_2$ ∩ Π$_2$.
Em 1983, Michael Sipser mostrou que BPP está contida na hierarquia de tempo polinomial. Péter Gács mostrou que BPP está atualmente inserida em Σ$_2$ ∩ Π$_2$. Clemens Lautemann contribuiu dando uma prova simples de que BPP está contida em Σ$_2$ ∩ Π$_2$, também em 1983. Conjectura-se que, na realidade, BPP = P, que é uma afirmação mais forte do que o teorema de Sipser-Lautemann.

## Prova

Aqui apresentamos a prova de Lautemann, distinguindo as partes acerca da inserção na hierarquia polinomial e em Σ$_2$.

### Contenção de BPP na hierarquia polinomial

Esta é a primeira parte provada por Michael Sipser. Sem perda de generalidade, uma máquina M ∈ BPP com erro ≤ 2$^{-|x|}$ é escolhida. (Todo problema BPP pode ser amplificado para reduzir a probabilidade de erro de modo exponencial). A ideia básica da prova é definir uma sentença Σ$_2$ ∩ Π$_2$ que é equivalente a dizer que x está na linguagem L definida por M usando um conjunto de transformações das variáveis aleatórias de entrada.
Desde que a saída de M dependa de uma entrada aleatória, assim como a entrada x, é útil definir que cadeias aleatórias produzem a saída correta como A(x) = {r | M(x,r) aceita}. A chave da prova é notar que quando x ∈ L, A(x) é muito grande e quando x ∉ L, A(x) é muito pequena. 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 destas transformações irá conter todo o espaço de cadeias de entrada aleatórias. Utilizando este fato, uma sentença Σ$_2$ e uma sentença Π$_2$ podem gerar verdadeiro, se somente se, x ∈ L (ver corolário).

#### Lema 1

A ideia geral do primeiro lema é provar que se A(x) cobre uma grande parte do espaço aleatório $R=\{1,0\}^{|r|}$ então existe um pequeno conjunto de traduções que cobrirá todo o espaço aleatório. Em uma linguagem mais matemática:
    se ${\frac {|A(x)|}{|R|}}>1-{\frac {1}{2^{|x|}}}$, então $\exists t_{1},t_{2},\ldots ,t_{|r|}$, quando $t_{i}\in \{1,0\}^{|r|}\$ tal que $\bigcup _{i}A(x)\oplus t_{i}=R.$
Prova. Escolha aleatoriamente t$_1$, t$_2$, ..., t$_{|r|}$. Faça $S=\bigcup _{i}A(x)\oplus t_{i}$ (a união de todas as transformações de A(x)).
Então, para todo r em R,
    $\Pr[r\notin S]=\Pr[r\notin A(x)\oplus t_{1}]\cdot \Pr[r\notin A(x)\oplus t_{2}]\cdots \Pr[r\notin A(x)\oplus t_{|r|}]\leq {\frac {1}{2^{|x|\cdot |r|}}}.$
A probabilidade de existir pelo menos um elemento em R e não em S é,
    $\Pr {\Bigl\bigvee _{i}(r_{i}\notin S){\Bigr ]}\leq \sum _{i}{\frac {1}{2^{|x|\cdot |r|}}}={\frac {1}{2^{|x|}}}<1.$
Portanto,
    $\Pr[S=R]\geq 1-{\frac {1}{2^{|x|}}}.$
Então existe uma seleção para cada $t_{1},t_{2},\ldots ,t_{|r|}$ tal que
    $\bigcup _{i}A(x)\oplus t_{i}=R.$

#### Lema 2

O teorema anterior mostra que A(x) pode cobrir todos os pontos possíveis no espaço usando um pequeno conjunto de traduções. Complementarmente a isto, para x ∉ L apenas uma pequena fração do espaço é coberta por A(x). Portanto, o conjunto de cadeias aleatórias que torna M(x,r) uma aceitação não pode ser gerado por um conjunto pequeno de vetores t$_i$.
    $R=\bigcup _{i}A(x)\oplus t_{i}$
R é o conjunto de todas as cadeias aleatórias de aceitação, “ou-exclusivadas” com vetores t$_i$.
    ${\frac {|A(x)|}{|R|}}\leq {\frac {1}{2^{|k|}}}\implies \neg \exists t_{1},t_{2},\dots ,t_{r}$

#### Corolário

Um corolário importante dos lemas mostra que o resultado da prova pode ser expresso como uma Σ$_2$, como segue.
    $x\in L\iff \exists t_{1},t_{2},\dots ,t_{|r|}\,\forall r\in R\bigvee _{1\leq i\leq |r|}(M(x,r\oplus t_{i}){\text{ accepts}}).$
Isto é, x está em uma linguagem L, se e somente se, existem vetores binários |r|, onde para todos os vetores de bit aleatórios r, a MT M aceita pelo menos um vetor aleatório ⊕ t$_i$.
A expressão acima está em Σ$_2$ de modo que ela é primeiro quantificada existencialmente e depois universalmente. Portanto, BPP ⊆ Σ$_{2.}$Como BPP é fechada sob complemento isto prova que BPP ⊆ Σ$_2$ ∩ Π$_{2.}$

### BPP está contida em Σ$_2$

Esta parte é a contribuição de Lautemann para o teorema.

#### Lemma 3

Baseado na definição de BPP nós mostramos o seguinte:
se L está em BPP, então, existe um algoritmo A tal que para todo x,
    ${\rm {Pr}}_{r}(A(x,r)={\mbox{right answer}})\geq 1-{\frac {1}{3m}},$
quando m é o número de bits aleatórios $|r|=m=|x|^{O(1)}$ e A executa em tempo $|x|^{O(1)}$.
Proof: Seja A' um algoritmo BPP para L. Para todo x, $\Pr _{r}(A'(x,r)={\mbox{wrong answer}})\leq 1/3$. A' usa m'(n) bits aleatórios onde n = |x|.Faça k(n) repetições de A' e aceite se, e somente se, pelo menos k(n)/2 execuções de A' aceitam. Defina esse novo algoritmo como A. Então A usa k(n)m'(n) bits aleatórios e,
    ${\rm {Pr}}_{r}(A(x,r)={\mbox{wrong answer}})\leq 2^{-ck(n)}.$
Podemos então achar k(n) com $k(n)=\Theta (\log m'(n))$ tal que,
    ${\frac {1}{2^{ck(n)}}}\leq {\frac {1}{3k(n)m'(n)}}.$

#### Teorema 1

Prova: Seja L em BPP e A como no Lema 3. Queremos mostrar que
    $x\in L\iff \exists y_{1},\dots ,y_{m}\in \{0,1\}^{m}\,\forall z\in \{0,1\}^{m}\bigvee _{i=1}^{m}A(x,y_{i}\oplus z)=1.$
Onde m é o número de bits aleatórios usados por A com entrada x. Dado $x\in L$, então,
    ${\begin{aligned}{\rm {Pr}}_{y_{1},\dots ,y_{m}}(\exists z&A(x,y_{1}\oplus z)=\dots =A(x,y_{m}\oplus z)=0)\\&\leq \sum _{z\in \{0,1\}^{m}}{\rm {Pr}}_{y_{1},\dots ,y_{m}}(A(x,y_{1}\oplus z)=\dots =A(x,y_{m}\oplus z)=0)\\&\leq 2^{m}{\frac {1}{(3m)^{m}}}\\&<1.\end{aligned}}$
Assim,
    ${\rm {Pr}}_{y_{1},\dots ,y_{m}}{\Bigl\forall z\bigvee _{i}A(x,y_{i}\oplus z){\Bigr )}=1-{\rm {Pr}}_{y_{1},...,y_{m}}(\exists zA(x,y_{1}\oplus z)=\dots =A(x,y_{m}\oplus z)=0).$
Assim $(y_{1},\dots ,y_{m})$ existe.
Reciprocamente, suponha $x\notin L$. Então
${\rm {Pr}}_{z}{\Bigl\bigvee _{i}A(x,y_{i}\oplus z){\Bigr )}\leq \sum _{i}{\rm {Pr}}_{z}(A(x,y_{i}\oplus z)=1)\leq m{\frac {1}{3m}}={\frac {1}{3}}.$
Assim,
    ${\rm {Pr}}_{z}(A(x,y_{1}\oplus z)=\dots =A(x,y_{m}\oplus z)=0)=1-{\rm {Pr}}_{z}{\Bigl\bigvee _{i}A(x,y_{i}\oplus z){\Bigr )}\geq {\frac {2}{3}}>0.$
Assim, existe um z tal que $\bigvee _{i}A(x,y_{i}\oplus z)=0$ para todo $y_{1},...,y_{m}\in \{0,1\}^{m}.$

## Versão Mais Forte (Fortalecimento da Versão)

O teorema pode ser fortalecido para ${\mathsf {BPP}}\subseteq {\mathsf {MA}}\subseteq {\mathsf {S}}_{2}^{P}\subseteq \Sigma _{2}\cap \Pi _{2}$ (vee MA, SP 2).