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 $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}}.$