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.^[1] 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.^[2] 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,^[2] 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.^[1] 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 ${\displaystyle 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 ${\displaystyle {\frac {|A(x)|}{|R|}}>1-{\frac {1}{2^{|x|}}}}$, então ${\displaystyle \exists t_{1},t_{2},\ldots ,t_{|r|}}$, quando ${\displaystyle t_{i}\in \{1,0\}^{|r|}\ }$ tal que ${\displaystyle \bigcup _{i}A(x)\oplus t_{i}=R.}$

Prova. Escolha aleatoriamente t₁, t₂, ..., t_|r|. Faça ${\displaystyle 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,

${\displaystyle \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 é,

${\displaystyle \Pr {\Bigl [}\bigvee _{i}(r_{i}\notin S){\Bigr ]}\leq \sum _{i}{\frac {1}{2^{|x|\cdot |r|}}}={\frac {1}{2^{|x|}}}<1.}$

Portanto,

${\displaystyle \Pr[S=R]\geq 1-{\frac {1}{2^{|x|}}}.}$

Então existe uma seleção para cada ${\displaystyle t_{1},t_{2},\ldots ,t_{|r|}}$ tal que

${\displaystyle \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.

${\displaystyle 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.

${\displaystyle {\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.

${\displaystyle 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,

${\displaystyle {\rm {Pr}}_{r}(A(x,r)={\mbox{right answer}})\geq 1-{\frac {1}{3m}},}$

quando m é o número de bits aleatórios ${\displaystyle |r|=m=|x|^{O(1)}}$ e A executa em tempo ${\displaystyle |x|^{O(1)}}$.

Proof: Seja A' um algoritmo BPP para L. Para todo x, ${\displaystyle \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,

${\displaystyle {\rm {Pr}}_{r}(A(x,r)={\mbox{wrong answer}})\leq 2^{-ck(n)}.}$

Podemos então achar k(n) com ${\displaystyle k(n)=\Theta (\log m'(n))}$ tal que,

${\displaystyle {\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

${\displaystyle 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 ${\displaystyle x\in L}$, então,

${\displaystyle {\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,

${\displaystyle {\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 ${\displaystyle (y_{1},\dots ,y_{m})}$ existe.

Reciprocamente, suponha ${\displaystyle x\notin L}$. Então

${\displaystyle {\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,

${\displaystyle {\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  ${\displaystyle \bigvee _{i}A(x,y_{i}\oplus z)=0}$ para todo ${\displaystyle y_{1},...,y_{m}\in \{0,1\}^{m}.}$

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

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

Referências