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 $\mathrm{\exists }{t}_1,t_2,\dots ,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,

$\mathrm{Pr}[r\notin S]=\mathrm{Pr}[r\notin A(x)\oplus t_1]\cdot \mathrm{Pr}[r\notin A(x)\oplus t_2]\cdots \mathrm{Pr}[r\notin A(x)\oplus t_{|r|}]\le \frac{1}{2^{|x|\cdot |r|}}.$

A probabilidade de existir pelo menos um elemento em R e não em S é,

$\mathrm{Pr}[\underset{i}{\bigvee }(r_i\notin S)]\le \sum _i\frac{1}{2^{|x|\cdot |r|}}=\frac{1}{2^{|x|}}<1.$

Portanto,

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

Então existe uma seleção para cada $t_1,t_2,\dots ,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|}\le \frac{1}{2^{|k|}}⟹\mathrm{\neg }\mathrm{\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⟺\mathrm{\exists }{t}_1,t_2,\dots ,t_{|r|}\mathrm{\forall }r\in R\underset{1\le i\le |r|}{\bigvee }(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,

${\mathrm{P}\mathrm{r}}_r(A(x,r)=\text{right answer})\ge 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 APredefinição:' um algoritmo BPP para L. Para todo x, $\underset{r}{\mathrm{Pr}}(A^{\prime }(x,r)=\text{wrong answer})\le 1/3$. APredefinição:' usa mPredefinição:'(n) bits aleatórios onde n = |x|.Faça k(n) repetições de APredefinição:' e aceite se, e somente se, pelo menos k(n)/2 execuções de APredefinição:' aceitam. Defina esse novo algoritmo como A. Então A usa k(n)mPredefinição:'(n) bits aleatórios e,

${\mathrm{P}\mathrm{r}}_r(A(x,r)=\text{wrong answer})\le 2^{-ck(n)}.$

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

$\frac{1}{2^{ck(n)}}\le \frac{1}{3k(n)m^{\prime }(n)}.$

Teorema 1

Prova: Seja L em BPP e A como no Lema 3. Queremos mostrar que

$x\in L⟺\mathrm{\exists }{y}_1,\dots ,y_m\in \{0,1{\}}^m\mathrm{\forall }z\in \{0,1{\}}^m\underset{i=1}{\overset{m}{\bigvee }}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{array}{cc}{\mathrm{P}\mathrm{r}}_{y_1,\dots ,y_m}(\mathrm{\exists }z& A(x,y_1\oplus z)=\dots =A(x,y_m\oplus z)=0)\\ & \le \sum _{z\in \{0,1{\}}^m}{\mathrm{P}\mathrm{r}}_{y_1,\dots ,y_m}(A(x,y_1\oplus z)=\dots =A(x,y_m\oplus z)=0)\\ & \le 2^m\frac{1}{(3m{)}^m}\\ & <1.\end{array}$

Assim,

${\mathrm{P}\mathrm{r}}_{y_1,\dots ,y_m}(\mathrm{\forall }z\underset{i}{\bigvee }A(x,y_i\oplus z))=1-{\mathrm{P}\mathrm{r}}_{y_1,...,y_m}(\mathrm{\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

${\mathrm{P}\mathrm{r}}_z(\underset{i}{\bigvee }A(x,y_i\oplus z))\le \sum _i{\mathrm{P}\mathrm{r}}_z(A(x,y_i\oplus z)=1)\le m\frac{1}{3m}=\frac{1}{3}.$

Assim,

${\mathrm{P}\mathrm{r}}_z(A(x,y_1\oplus z)=\dots =A(x,y_m\oplus z)=0)=1-{\mathrm{P}\mathrm{r}}_z(\underset{i}{\bigvee }A(x,y_i\oplus z))\ge \frac{2}{3}>0.$

Assim, existe um z tal que  $\underset{i}{\bigvee }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 $𝖡𝖯𝖯\subseteq 𝖬𝖠\subseteq {𝖲}_2^P\subseteq {\mathrm{\Sigma }}_2\cap {\mathrm{\Pi }}_2$ (vee MA, [[S2P (complexity)|SPredefinição:Su]]).