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

Representação geral de um protocol de prova interativa.

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₀ 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₁, ..., b_n) para uma fórmula polinomial p_φ(x₁, ..., 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₁, ..., b_n) para uma formula polinomial p_φ(x₁, ..., 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ⁿ; 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₀ é o número que satisfaz o valor de φ. f₀ é uma função void, sem variáveis.

Agora, o protodolo para #SAT funciona como segue:

• Fase 0: A provadora P escolhe q > 2ⁿ e computa f, e então aplica o prilitivoq e f₀ ao verificador V. V checa que q é um primitivo max(1000, 2ⁿ) e que f₀() = k.

• Fase 1: P envias os coeficientes de f₁(z) como um polinomial de z. V verifica que o grau de f₁ é menor que n e que f₀ = f₁(0) + f₁(1). (Se não, V rejeita). V então manda um número randômico r₁ 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₁ 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ⁿ a chance de r₁ ser um desses valores é de $n/2^{n}<n/n^{3}$ se n > 10, ou no máximo (n/1000) ≤ (n/n³) 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₁, ..., a_i) é φ com a₁ para a_i substituido por x₁ para x_i. Então f₀ é 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₁, ..., 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₀ ainda é o valor verdade de ψ, mas o valor de R_x produz um resultado que é linearmente em x. Também, sobre qualquer Q_ix_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⁴ aonde n é o tamanho de ψ.

• Fase 0: P → V: P envia f₀ para V. V checa se f₀= 1 e rejeita se não for.
• Fase 1: P → V: P manda f₁(z) para V. V usa coeficientes para valorar f₁(0) e f₁(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₁ 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₀. 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²) 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.

Bibliografia

• Babai, L. Trading group theory for randomness. In Proceedings of the 17th ACM Symposium on the Theory of Computation . ACM, New York, 1985, pp. 421–429.
• Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The Knowledge complexity of interactive proof-systems. Proceedings of 17th ACM Symposium on the Theory of Computation, Providence, Rhode Island. 1985, pp. 291–304. Extended abstract
• Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. Proceedings of the 18th Annual ACM Symposium on Theory of Computation. ACM, New York, 1986, pp. 59–68.
• Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous. QIP = PSPACE. [1]
• Lund, C., Fortnow, L., Karloff, H., Nisan, N. Algebraic methods for interactive proof systems. In Proceedings of 31st Symposium on the Foundations of Computer Science. IEEE, New York, 1990, pp. 2–90.
• Adi Shamir. IP = PSPACE. Journal of the ACM, volume 39, issue 4, p. 869–877. October 1992.
• Alexander Shen. IP=PSpace: Simplified Proof. J.ACM, v. 39(4), pp. 878–880, 1992.
• MIP, IPP, QIP, QIP(2), compIP, frIP