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 Σ₂ ∩ Π₂.

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 Σ₂ ∩ Π₂. Clemens Lautemann contribuiu dando uma prova simples de que BPP está contida em Σ₂ ∩ Π₂, 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 Σ₂.

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 Σ₂ ∩ Π₂ 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 Σ₂ e uma sentença Π₂ 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₁, t₂, ..., 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 Σ₂, 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 Σ₂ de modo que ela é primeiro quantificada existencialmente e depois universalmente. Portanto, BPP ⊆ Σ_2. Como BPP é fechada sob complemento isto prova que BPP ⊆ Σ₂ ∩ Π_2.

BPP está contida em Σ₂

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).