# IP (complexidade)

Em Teoria da complexidade computacional, a classe IP (abreviação de Interactive Polynomial Time (Tempo Polinomial Interativo)) é a classe de problemas solúveis em tempo polinomial por um sistema de prova interativa. O conceito de sistemas de provas interativas foi introduzido pela primeira vez por Shafi Goldwasser, Silvio Micali, e Charles Rackoff em 1985. Um sistema de prova interativa consiste em duas máquinas, uma provadora (P) a qual apresenta a prova que uma dada string n é um membro de uma certa linguagem e um verificador (V) o qual verifica se a prova apresentada é correta. Assumindo que a provadora é infinita em armazenamento e computação, enquanto o verificador é uma máquina com tempo polinomial probabilístico com acesso a uma string de bits aleatórios cujo tamanho é polinomial no tamanho n. Essas duas máquinas trocam um número polinomial, p(n), de mensagens e uma vez que a interação é concluída, o verificador deve decidir se n está ou não na linguagem, com apenas 1/3 de chance de erro. (Então, qualquer linguagem em BPP está em IP, sendo assim o verificador poderia simplesmente ignorar o provador e fazer a decisão por conta própria).

## Definição

A linguagem L pertence a IP se existe um V, P para todo Q, w:
    $w\in L\Rightarrow \Pr[V\leftrightarrow P{\text{ aceita }}w]\geq {\tfrac {2}{3}}$
    $w\not \in L\Rightarrow \Pr[V\leftrightarrow Q{\text{ aceita }}w]\leq {\tfrac {1}{3}}$
O Protocolo de Arthur-Merlin, introduzido por Laszlo Babai, é similar em natureza, exceto que o número de rodadas de interação é limitado por uma constante ao invés de um polinômio.
Goldwasser et al. mostraram que protocolos de "moeda pública", onde os números randômicos usados por um verificador são providos ao provador juntamente com os desafios, não são menos poderosos do que protocolos de moeda privada. No máximo duas rodadas adicionais de interação são necessárias para replicar o efeito de um protocolo de moeda privada. A inclusão oposta é direta, porque o verificador sempre pode mandar para o provador os resultados dos seus lançamentos de moeda privada, que prova que os dois tipos de protocolos são equivalentes.
Na seção seguinte iremos provar que IP = PSPACE, um teorema importante em complexidade computacional, que demonstra que um sistema de prova interativa pode ser usado para decidir se uma string é um membro de uma linguagem em tempo polinomial, mesmo que a prova PSPACE tradicional seja exponencialmente longa.

## Prova que IP = PSPACE

A prova pode ser dividida em duas partes, mostramos que IP ⊆ PSPACE e PSPACE ⊆ IP. A intuição nesta prova é que polinômios formam bons códigos para corretores de erros. Meir mostrou que isso pode ser feito com alta precisão: com algum trabalho extra a prova pode ser modificada para provar coisas mais abstratas e indiscutivelmente mais naturais, como configurações de códigos corretores de erro.

### IP ⊆ PSPACE

A fim de demonstrar que IP ⊆ PSPACE, nós apresentamos a simulação de um sistema de prova interativa via uma máquina que usa espaço polinomial. Agora vamos as devidas definições:
    $\Pr[V{\text{ aceita }}w{\text{ começando em }}M_{j}]=\max \nolimits _{P}\Pr \left[V\leftrightarrow P{\text{ aceita }}w{\text{ começando em }}M_{j}\right]$
e para todo 0 ≤ j ≤ p e toda história de mensagens M$_j$, definimos indutivamente a função N$_{Mj}$:
    $N_{M_{j}}={\begin{cases}0&j=p{\text{ e }}m_{p}={\text{rejeita}}\\1&j=p{\text{ e }}m_{p}={\text{aceita}}\\\max _{m_{j+1}}N_{M_{j+1}}&j<p{\text{ e }}j{\text{ é impar}}\\{\text{wt-med}}_{m_{j+1}}N_{M_{j+1}}&j<p{\text{ e }}j{\text{ é par}}\\\end{cases}}$
onde:
    ${\text{wt-med}}_{m_{j+1}}N_{M_{j+1}}:=\sum \nolimits _{m_{j+1}}\Pr \nolimits _{r}[V(w,r,M_{j})]$
onde Pr$_r$ é a probabilidade tomada sobre a cadeia aleatória r de tamanho p. Essa expressão é a média de N$_{Mj+1}$, com peso determinado pela probabilidade que o verificador mande a mensagem m$_{j+1}$.
Suponha que M$_0$ seja a mensagem de sequência vazia, aqui vamos mostrar que N$_{M0}$ = Pr[V aceita w]. Primeiro, para computar N$_{M0}$, um algoritmo pode recursivamente calcular os valores N$_{Mj}$ para todo j e M$_j$. Uma vez que a pilha da recursão é de tamanho p, onde espaço polinomial é necessário. O segundo requisito é que precisamos N$_{M0}$ = Pr[V aceita w], o valor necessário para determinar se w pertence a A. Usamos indução para provar isso.
Temos que mostrar que para todo 0 ≤ j ≤ p e todo M$_j$ N$_{Mj}$ = Pr[V aceita w começando em M$_j$], e vamos fazer isso usando indução em j. O caso base é provar para j = p. Então vamos usar indução para ir de p até chegar no 0.
O caso base j = p é bem simples. Uma vez que m$_p$ é ou aceito ou é rejeitado, se m$_p$ é aceito, N$_{Mp}$ é definido como sendo 1 e Pr[V aceita w começando em M$_j$] = 1 uma vez que a cadeia de mensagens indica aceitação, então a afirmação é verdadeira. Usamos o argumento similar a esse para o caso de m$_p$ ser rejeitado.
Para a hipótese de indução assumimos que para j+1 ≤ p e uma sequência de mensagens M$_{j+1}$, N$_{Mj}$ = Pr[V aceita w começando em j+1] e então provamos a hipótese para j e para a sequência de mensagens M$_j$.
Se j é par, m$_{j+1}$ é uma mensagem de V para P. Pela definição de N$_{Mj}$,
    $N_{M_{j}}=\sum \nolimits _{m_{j+1}}\Pr \nolimits _{r}\left[V(w,r,M_{j})=m_{j+1}\right]N_{M_{j+1}}.$
Então, pela hipótese indutiva, podemos dizer que é igual a
    $\sum \nolimits _{m_{j+1}}\Pr \nolimits _{r}\left[V(w,r,M_{j})=m_{j+1}\right]*\Pr \left[V{\text{ aceita }}w{\text{ começando em }}M_{j+1}\right].$
Finalmente, pela definição, nós podemos ver que isso é igual a Pr[V aceita w começando em M$_j$].
Se j é impar, m$_{j+1}$ é uma mensagem de P para V. Pela definição, temos:
    $N_{M_{j}}=\max \nolimits _{m_{j+1}}N_{M_{j+1}}.$
Então, pela hipótese indutiva, é igual a:
    $\max \nolimits _{m_{j+1}}*\Pr[V{\text{ aceita }}w{\text{ começando em }}M_{j+1}].$
Isso é igual a Pr[V accepts w começando em M$_j$], uma vez que:
    $\max \nolimits _{m_{j+1}}\Pr[V{\text{ aceita }}w{\text{ começando em }}M_{j+1}]\leq \Pr[V{\text{ aceita w começando em }}M_{j}]$
por que a provadora do lado esquerdo poderia mandar a mensagem m$_{j+1}$ para maximizar a expressão no lado esquerdo. E:
    $\max \nolimits _{m_{j+1}}\Pr \left[V{\text{ aceita }}w{\text{ começando em }}M_{j+1}\right]\geq \Pr \left[V{\text{ aceita }}w{\text{ começando em }}M_{j}\right]$
Uma vez que a mesma Máquina Provadora não pode fazer nada mais do que mandar a mesma mensagem. Então isso assegura que é válido independentemente se i é par ou ímpar. A prova de que IP ⊆ PSPACE está completa.
Construímos uma máquina de espaço polinomial que usa a melhor provadora P para uma string w em uma linguagem A. Usamos essa melhor Provadora em lugar de uma provadora com entrada de bits aleatórios pois isso nos possibilita tentar todos os conjuntos de entradas de bits aleatórios com uma máquina de espaço polinomial, mostramos que IP ⊆ PSPACE, como desejado.

### PSPACE ⊆ IP

Para ilustrar a técnica que vai ser usada para provar IP ⊆ PSPACE, primeiro vamos provar um teorema mais fraco, que foi provado por Lund, et al.: #SAT ∈ IP. Daí então, usando os conceitos dessa prova, podemos estendê-la para mostrar que TQBF ∈ IP. Uma vez que TQBF ∈ PSPACE-completo, e TQBF ∈ IP então PSPACE ⊆ IP.

#### #SAT é um membro de IP

Começamos mostrando que #SAT está em IP, aonde:
    $\#{\text{SAT}}=\left\{\langle \varphi ,k\rangle \ :\ \varphi {\text{ é uma fórmula CNH com exatamente }}k{\text{ atribuições satisfeitoras}}\right\}.$
Perceba que isso é diferente da definição normal de #SAT, aqui é uma problema de decisão ao invés de uma função.
Primeiro mostramos o uso da aritmetização para mapear a fórmula booleana com n variáveis, φ(b$_1$, ..., b$_n$) para uma fórmula polinomial p$_φ$(x$_1$, ..., x$_n$), onde p$_φ$ imita φ em p$_φ$ é 1 se φ é verdadeiro e 0 caso contrário, mostrado isso, temos que às variáveis de p$_φ$ são atribuídos valores booleanos. As operações booleanas ∨, ∧ e ¬ usadas em φ são simuladas em p$_φ$ atráves da substituição dos operadores em φ como mostrado na tabela abaixo.
Regras de Aritmetização para converter formulas booleanas φ(b$_1$, ..., b$_n$) para uma formula polinomial p$_φ$(x$_1$, ..., x$_n$) :
| a ∧ b | ab |
| a ∨ b | a ∗ b := 1 − (1 − a)(1 − b) |
| ¬a | 1 − a |
Como um exemplo, φ = a ∧ b ∨ ¬c pode ser convertido em uma formula booleana da seguinte forma:
    ${\begin{aligned}p_{\varphi }&=a\wedge b\vee \neg c\\&=a\wedge \left(b*(1-c)\right)\\&=a\wedge \left(1-(1-b)(1-(1-c))\right)\\&=a\left(1-(1-b)(1-(1-c))\right)\\&=a-(ac-abc)\end{aligned}}$
As operações ab e a ∗ b cada uma resulta em um polinômio com um grau limitado pela soma dos graus dos polinômios para a and b e a partir daí, o grau de qualquer variável é no máximo o tamanho de φ.
Seja F um número finito de ordem q > 2$^n$; com q maior que 1000. Para cada 0 ≤ i ≤ n,defina uma função f$_i$ em F, tendo como parâmetros $a_{1},\dots ,a_{i-1}\in F$, e um variável a$_i$ em F: Para 0 ≤ i ≤ n e para $a_{1},\dots ,a_{i}\in F$ seja
    $f_{i}(a_{1},\dots ,a_{i})=\sum \nolimits _{a_{i+1},\dots ,a_{n}\in \{0,1\}}p(a_{1},\dots ,a_{n}).$
Note que o valor de f f$_0$ é o número que satisfaz o valor de φ. f$_0$ é uma função void, sem variáveis.
Agora, o protodolo para #SAT funciona como segue:
* Fase 0: A provadora P escolhe q > 2$^n$ e computa f, e então aplica o prilitivoq e f$_0$ ao verificador V. V checa que q é um primitivo max(1000, 2$^n$) e que f$_0$ = k.
* Fase 1: P envias os coeficientes de f$_1$(z) como um polinomial de z. V verifica que o grau de f$_1$ é menor que n e que f$_0$ = f$_1$(0) + f$_1$(1). (Se não, V rejeita). V então manda um número randômico r$_1$ de F para P.
* Fase i: P envia os coeficientes de $f_{i}(r_{1},\dots ,r_{i-1},z)$ como um polinômio de z. V verifica que o grau de f$_i$ é menor que n e que $f_{i-1}(r_{1},\dots ,r_{i-1})=f_{i}(r_{1},\dots ,r_{i-1},0)+f_{i}(r_{1},\dots ,r_{i-1},1)$. (Se não, V rejeita). V então manda um número randômico r$_i$ de F para P.
* Fase n+1: V valora $p(r_{1},\dots ,r_{n})$ para comparar com valor $f_{n}(r_{1},\dots ,r_{n})$. Se eles forem iguais V aceita, rejeita caso contrário.
Note que isso é um algoritmo de moeda pública.
Se φ tem k valorações que satisfazem, é claro que V irá aceitá-la. Se φ não possui k valorações que a satisfazem, existe uma prova ${\tilde {P}}$ que tenta convencer V que φ não possui k valorações que satisfazem. Mostramos que isso só pode ser feito com baixa probabilidade.
De forma a impedir V de rejeitar na fase 0, ${\tilde {P}}$ tem que mandar valores incorretos ${\tilde {f}}_{0}$ para P. Então, na fase 1, ${\tilde {P}}$ deve mandar um polinomial incorreto ${\tilde {f}}_{1}$ com a propriedade de ${\tilde {f}}_{1}(0)+{\tilde {f}}_{1}(1)={\tilde {f}}_{0}$. Quando V escolhe o número aleatório r$_1$ para mandar para P,
    $\Pr \left[{\tilde {f}}_{1}(r_{1})=f_{1}(r_{1})\right]<{\tfrac {1}{n^{2}}}.$
Isso acontece porque um polinômio com uma só variável de grau no máximo d não pode ter mais que d raizes (a não ser que sempre gere o valor 0). Então, qualquer dois polinômios em uma váriavel de grau no máximo d podem ser iguais em no máximo d vezes. Uma vez que |F| > 2$^n$ a chance de r$_1$ ser um desses valores é de $n/2^{n}<n/n^{3}$ se n > 10, ou no máximo (n/1000) ≤ (n/n$^3$) se n ≤ 10.
Generalizando essa ideia para outras fases temos que para cada 1 ≤ i ≤ n se
    ${\tilde {f}}_{i-1}(r_{1},\dots ,r_{i-1})\neq f_{i-1}(r_{1},\dots ,r_{i-1}),$
então para r$_i$ escolhido aleatoriamente em F,
    $\Pr \left[{\tilde {f}}(r_{1},\dots ,r_{i})=f_{i}(r_{1},\dots ,r_{i})\right]\leq {\tfrac {1}{n^{2}}}.$
Existem n fases, então a probabilidade que ${\tilde {P}}$ é sortudo por que V seleciona em algum estágio um r$_i$ conveniente é no maximo 1/n. Então, nenhum provador pode fazer o verificador aceitar com probabilidade maior que 1/n. Podemos perceber também dessa definição que o verificador V opera em tempo polinomial probabilístico. Logo, #SAT ∈ IP.

#### TQBF é um membro de IP

Para mostrar que PSPACE é um subconjunto de IP precisamos mostrar um problema PSPACE-completo e mostrar que ele está em IP. Uma vez que nós mostrarmos isso, fica evidente que PSPACE ⊆ IP. Os créditos da técnica demonstrada aqui são atribuídos a Adi Shamir.
Sabemos que TQBF está em PSPACE-Complete. Seja ψ uma expressão booleana quantificada:
    $\psi =Q_{1}x_{1}\dots Q_{m}x_{m}[\varphi ]$
onde φ está na forma CNF. Então Q$_i$ é o quantificador, que pode ser tanto ∃ ou ∀. Agora f$_i$ é o mesmo que na prova anterior, mas agora ele também inclui quantificadores.
    $f_{i}(a_{1},\dots ,a_{i})={\begin{cases}f_{i}(a_{1},\dots ,a_{m})=1&Q_{i+1}x_{i+1}\dots Q_{m}x_{m}[\varphi (a_{1},\dots ,a_{i})]{\text{ se for verdade}}\\0&{\text{em caso contrário}}\end{cases}}$
Aqui, φ(a$_1$, ..., a$_i$) é φ com a$_1$ para a$_i$ substituido por x$_1$ para x$_i$. Então f$_0$ é valor verdade de ψ. Com o objetivo de fazer a aritmetização ψ devemos usar as regras seguintes:
    $f_{i}(a_{1},\dots ,a_{i})={\begin{cases}f_{i+1}(a_{1},\dots ,a_{i},0)\cdot f_{i+1}(a_{1},\dots ,a_{i},1)&Q_{i+1}=\forall \\f_{i+1}(a_{1},\dots ,a_{i},0)*f_{i+1}(a_{1},\dots ,a_{i},1)&Q_{i+1}=\exists \end{cases}}$
que como anteriormente, definimos x ∗ y = 1 − (1 − x)(1 − y).
Usando o método definido em #SAT, devemos enfrentar o problema que para qualquer f$_i$ o grau do polinômio resultante pode dobrar com cada quantificador. Para impedir isso, devemos introduzir um novo operador de redução R no qual vai reduzir os graus dos polinômios sem trocar seu comportamento em entradas booleanas.
Então, agora antes da aritmetização $\psi =Q_{1}x_{1}\dots Q_{m}x_{m}[\varphi ]$ introduzimos uma nova expressão:
    $\psi '=Q_{1}x_{1}Rx_{1}Q_{2}Rx_{1}Rx_{2}\dots Q_{m}Rx_{1}\dots Rx_{m}[\varphi ]$
onde r:
    $\psi '=S_{1}y_{1}\dots S_{k}y_{k}[\varphi ],\qquad {\text{ where }}S_{i}\in \{\forall ,\exists ,R\},\ y_{i}\in \{x_{1},\dots ,x_{m}\}$
Agora para cada i ≤ k nós definimos a função f$_i$. nós também definimos $f_{k}(x_{1},\dots ,x_{m})$ para ser o polinômio p(x$_1$, ..., x$_m$) que é obtido através da aritmetização de φ. Para manter o grau dos polinômios baixos, definimos f$_i$ em termos de f$_{i+1}$:
    ${\text{If }}S_{i+1}=\forall ,\quad f_{i}(a_{1},\dots ,a_{i})=f_{i+1}(a_{1},\dots ,a_{i},0)\cdot f_{i+1}(a_{1},\dots ,a_{i},1)$
    ${\text{If }}S_{i+1}=\exists ,\quad f_{i}(a_{1},\dots ,a_{i})=f_{i+1}(a_{1},\dots ,a_{i},0)*f_{i+1}(a_{1},\dots ,a_{i},1)$
    ${\text{If }}S_{i+1}=R,\quad f_{i}(a_{1},\dots ,a_{i},a)=(1-a)f_{i+1}(a_{1},\dots ,a_{i},0)+af_{i+1}(a_{1},\dots ,a_{i},1)$
Agora podemos ver que a operação de redução R, não muda o grau do polinômio. Também é importante perceber que a operação R$_x$ não muda o valor da função nas entradas booleanas. Então, f$_0$ ainda é o valor verdade de ψ, mas o valor de R$_x$ produz um resultado que é linearmente em x. Também, sobre qualquer Q$_i$x$_i$ nós adicionamos $R_{x_{1}}\dots R_{x_{i}}$ em ψ′ a fim de reduzir o grau para 1 depois da aritmetização Q$_i$
Agora vamos descrever o protocolo. Se n é o tamanho de ψ, toda operação aritmética no protocolo é sobre o tamanho no mínimo n$^4$ aonde n é o tamanho de ψ.
* Fase 0: P → V: P envia f$_0$ para V. V checa se f$_0$= 1 e rejeita se não for.
* Fase 1: P → V: P manda f$_1$(z) para V. V usa coeficientes para valorar f$_1$(0) e f$_1$(1). Então ele checa se os graus de polinomios é no máximo n e que a seguinte identidade é verdadeira:
       $f_{0}={\begin{cases}f_{1}(0)\cdot f_{1}(1)&{\text{ se }}S=\forall \\f_{1}(0)*f_{1}(1)&{\text{ se }}S=\exists .\\(1-r)f_{1}(0)+rf_{1}(1)&{\text{ se }}S=R.\end{cases}}$
    Se algum falha, entao rejeite
* Phase i: P → V: P envia$f_{i}(r_{1},\dots ,r_{i-1},z)$ como um polinômio em z. r$_1$ mostra que o anterior passou valores aleatórios para $r_{1},\dots ,r_{i-1}$
V usa coeficientes para valorar $f_{i}(r_{1},\dots ,r_{i-1},0)$ e $f_{i}(r_{1},\dots ,r_{i-1},1)$. Entâo ele checa se o grau do polinômio é no máximo n e a seguinte identidade é verdadeira:
    $f_{i-1}(r_{1},\dots ,r_{i-1})={\begin{cases}f_{i}(r_{1},\dots ,r_{i-1},0)\cdot f_{i}(r_{1},\dots ,r_{i-1},1)&S=\forall \\f_{i}(r_{1},\dots ,r_{i-1},0)*f_{i}(r_{1},\dots ,r_{i-1},1)&S=\exists .\end{cases}}$
    $f_{i-1}(r_{1}\dots r)=(1-r)f_{i}(r_{1},\dots ,r_{i-1},0)+rf_{i}(r_{1},\dots ,r_{i-1},1){\text{ se }}S=R.$
    Se alguma delas falha, entao rejeite.
V → P: V escolhe um r aleatório em F e manda para P. (Se S=R então o valor de r substitiu o valor anterior de r).
Vá para a fase i + 1 aonde P deve induzir V que $f_{i}(r_{1},\dots ,r)$ é correto.
* Fase k + 1: V valora$p(r_{1},\dots ,r_{m})$. Então ele checa se $p(r_{1},\dots ,r_{m})=f_{k}(r_{1},\dots ,r_{m})$ Se eles são iguais, então V aceita, V rejeita, caso contrário.
Esse é o fim da descrição do protocolo.
Se ψ é verdade, então V vai aceitar quanto P segue o protocolo. Assim como se ${\tilde {P}}$ é um provador malicioso no qual ele mente, e se ψ é falso, então ${\tilde {P}}$ vai precisar mentir na fase 0 e enviar algum valor para f$_0$. Se na fase i, V tem um valor incorreto para $f_{i-1}(r_{1},\dots )$ então $f_{i}(r_{1},\dots ,0)$ e $f_{i}(r_{1},\dots ,1)$ naturalmente, também vai ser incorreto , e assim por diante. A probabilidade para ${\tilde {P}}$ de ser sortudo o suficiente para o valor randômico de r é no máximo o grau do polinômio dividido pelo tamanho: $n/n^{4}$. O protocolo roda sobre O(n$^2$) fases, então a probabilidade que ${\tilde {P}}$ é sortudo em alguma fase é ≤ 1/n. Se ${\tilde {P}}$ nunca for sortudo, então V vai rejeitar na fase k+1.
Uma vez que nós mostramos IP ⊆ PSPACE ePSPACE ⊆ IP, nós podemos concluir que IP = PSPACE, como desejado. Além disso, nós mostramos que qualquer algoritmo IP pode ser de moeda-pública, uma vez que a redução de PSPACE para IP tem essa propriedade.