Saltar para o conteúdo

IP (complexidade)

Origem: Wikipédia, a enciclopédia livre.

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.

A linguagem L pertence a IP se existe um V, P para todo Q, w:

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

[editar | editar código-fonte]

A prova pode ser dividida em duas partes, mostramos que IPPSPACE e PSPACEIP. A intuição nesta prova é que polinômios formam bons códigos para corretores de erros. Meir mostrou que [1] 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

[editar | editar código-fonte]

A fim de demonstrar que IPPSPACE, 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:

e para todo 0 ≤ jp e toda história de mensagens Mj, definimos indutivamente a função NMj:

onde:

onde Prr é a probabilidade tomada sobre a cadeia aleatória r de tamanho p. Essa expressão é a média de NMj+1, com peso determinado pela probabilidade que o verificador mande a mensagem mj+1.

Suponha que M0 seja a mensagem de sequência vazia, aqui vamos mostrar que NM0 = Pr[V aceita w]. Primeiro, para computar NM0, um algoritmo pode recursivamente calcular os valores NMj para todo j e Mj. Uma vez que a pilha da recursão é de tamanho p, onde espaço polinomial é necessário. O segundo requisito é que precisamos NM0 = 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 ≤ jp e todo Mj NMj = Pr[V aceita w começando em Mj], 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 mp é ou aceito ou é rejeitado, se mp é aceito, NMp é definido como sendo 1 e Pr[V aceita w começando em Mj] = 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 mp ser rejeitado.

Para a hipótese de indução assumimos que para j+1 ≤ p e uma sequência de mensagens Mj+1, NMj = 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 Mj.

Se j é par, mj+1 é uma mensagem de V para P. Pela definição de NMj,

Então, pela hipótese indutiva, podemos dizer que é igual a

Finalmente, pela definição, nós podemos ver que isso é igual a Pr[V aceita w começando em Mj].

Se j é impar, mj+1 é uma mensagem de P para V. Pela definição, temos:

Então, pela hipótese indutiva, é igual a:

Isso é igual a Pr[V accepts w começando em Mj], uma vez que:

por que a provadora do lado esquerdo poderia mandar a mensagem mj+1 para maximizar a expressão no lado esquerdo. E:

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 IPPSPACE 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 IPPSPACE, como desejado.

PSPACE ⊆ IP

[editar | editar código-fonte]

Para ilustrar a técnica que vai ser usada para provar IPPSPACE, 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 PSPACEIP.

#SAT é um membro de IP

[editar | editar código-fonte]

Começamos mostrando que #SAT está em IP, aonde:

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, φ(b1, ..., bn) para uma fórmula polinomial pφ(x1, ..., xn), 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.

ab ab
ab ab := 1 − (1 − a)(1 − b)
¬a 1 − a
Regras de Aritmetização para converter formulas booleanas φ(b1, ..., bn) para uma formula polinomial pφ(x1, ..., xn)

Como um exemplo, φ = ab ∨ ¬c pode ser convertido em uma formula booleana da seguinte forma:

As operações ab e ab 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 > 2n; com q maior que 1000. Para cada 0 ≤ in,defina uma função fi em F, tendo como parâmetros , e um variável ai em F: Para 0 ≤ in e para seja

Note que o valor de f f0 é o número que satisfaz o valor de φ. f0 é uma função void, sem variáveis.

Agora, o protodolo para #SAT funciona como segue:

  • Fase 0: A provadora P escolhe q > 2n e computa f, e então aplica o prilitivoq e f0 ao verificador V. V checa que q é um primitivo max(1000, 2n) e que f0() = k.
  • Fase 1: P envias os coeficientes de f1(z) como um polinomial de z. V verifica que o grau de f1 é menor que n e que f0 = f1(0) + f1(1). (Se não, V rejeita). V então manda um número randômico r1 de F para P.
  • Fase i: P envia os coeficientes de como um polinômio de z. V verifica que o grau de fi é menor que n e que . (Se não, V rejeita). V então manda um número randômico ri de F para P.
  • Fase n+1: V valora para comparar com valor . 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 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, tem que mandar valores incorretos para P. Então, na fase 1, deve mandar um polinomial incorreto com a propriedade de . Quando V escolhe o número aleatório r1 para mandar para P,

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| > 2n a chance de r1 ser um desses valores é de se n > 10, ou no máximo (n/1000) ≤ (n/n3) se n ≤ 10.

Generalizando essa ideia para outras fases temos que para cada 1 ≤ in se

então para ri escolhido aleatoriamente em F,

Existem n fases, então a probabilidade que é sortudo por que V seleciona em algum estágio um ri 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

[editar | editar código-fonte]

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 PSPACEIP. 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:

onde φ está na forma CNF. Então Qi é o quantificador, que pode ser tanto ∃ ou ∀. Agora fi é o mesmo que na prova anterior, mas agora ele também inclui quantificadores.

Aqui, φ(a1, ..., ai) é φ com a1 para ai substituido por x1 para xi. Então f0 é valor verdade de ψ. Com o objetivo de fazer a aritmetização ψ devemos usar as regras seguintes:

que como anteriormente, definimos xy = 1 − (1 − x)(1 − y).

Usando o método definido em #SAT, devemos enfrentar o problema que para qualquer fi 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 introduzimos uma nova expressão:

onde r:

Agora para cada ik nós definimos a função fi. nós também definimos para ser o polinômio p(x1, ..., xm) que é obtido através da aritmetização de φ. Para manter o grau dos polinômios baixos, definimos fi em termos de fi+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 Rx não muda o valor da função nas entradas booleanas. Então, f0 ainda é o valor verdade de ψ, mas o valor de Rx produz um resultado que é linearmente em x. Também, sobre qualquer Qixi nós adicionamos em ψ′ a fim de reduzir o grau para 1 depois da aritmetização Qi

Agora vamos descrever o protocolo. Se n é o tamanho de ψ, toda operação aritmética no protocolo é sobre o tamanho no mínimo n4 aonde n é o tamanho de ψ.

  • Fase 0: PV: P envia f0 para V. V checa se f0= 1 e rejeita se não for.
  • Fase 1: PV: P manda f1(z) para V. V usa coeficientes para valorar f1(0) e f1(1). Então ele checa se os graus de polinomios é no máximo n e que a seguinte identidade é verdadeira:
Se algum falha, entao rejeite
  • Phase i: PV: P envia como um polinômio em z. r1 mostra que o anterior passou valores aleatórios para

V usa coeficientes para valorar e . Entâo ele checa se o grau do polinômio é no máximo n e a seguinte identidade é verdadeira:

Se alguma delas falha, entao rejeite.

VP: 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 é correto.

  • Fase k + 1: V valora. Então ele checa se 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 é um provador malicioso no qual ele mente, e se ψ é falso, então vai precisar mentir na fase 0 e enviar algum valor para f0. Se na fase i, V tem um valor incorreto para então e naturalmente, também vai ser incorreto , e assim por diante. A probabilidade para de ser sortudo o suficiente para o valor randômico de r é no máximo o grau do polinômio dividido pelo tamanho: . O protocolo roda sobre O(n2) fases, então a probabilidade que é sortudo em alguma fase é ≤ 1/n. Se nunca for sortudo, então V vai rejeitar na fase k+1.

Uma vez que nós mostramos IPPSPACE ePSPACEIP, 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.

Referências