Saltar para o conteúdo

Sistema de prova interativa

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

Na teoria da complexidade, um sistema de prova interativa é uma máquina abstrata que formula computação como a troca de mensagens entre duas partes. As duas partes, o verificador e o provador, interagem através da troca de mensagens, a fim de verificar se uma determinada cadeia pertence a uma linguagem ou não. O provador é muito poderoso e possui recursos computacionais ilimitados, mas não é confiável, enquanto que o verificador tem poder computacional limitado. Mensagens são enviadas entre o verificador e o provador até que o verificador tenha uma resposta ao problema e tenha "convencido" ele mesmo de que está correto.

Todas as provas de sistema interativo tem dois requisitos:

  • Completude: se a afirmação é verdadeira, o verificador (isto é, que segue o protocolo adequadamente) irá ser convencido deste fato por um provador honesto.
  • Corretude: se uma afirmação é falsa, nenhum provador, mesmo se ele não segue o protocolo, conseguirá convencer o verificador honesto de que isso é verdade, exceto com pequena probabilidade.

Assume-se que o verificador é sempre honesto.

A natureza específica do sistema, e assim a classe de complexidade das linguagens que podem ser reconhecidas, depende de que tipo de limites são colocados no verificador, bem como quais habilidades são dadas — por exemplo, muitos sistemas de provas interativas dependem criticamente da habilidade do verificador de fazer escolhas aleatórias. Isso também depende da natureza da mensagem trocada — quantas e quais eles podem conter. Sistemas interativos de prova foram encontrados para ter algumas implicações importantes para complexidade de classes tradicional definida usando somente máquinas. As principais classes de complexidade que descrevem sistemas de provas interativos são AM e IP.

NP

[editar | editar código-fonte]

A classe de complexidade NP deve ser revista como um sistema de prova simples. Nesse sistema, o verificador é uma máquina determinística de tempo polinomial (uma máquina P). Protocolo é:

  • O provador examina a entrada e computa a solução usando seu poder ilimitado e retorna um certificado de prova de tamanho polinomial.
  • O verificador verifica que o certificado é válido em tempo polinomial determinístico. Se ele é válido, aceite; caso contrário, rejeite.

No caso em que um certificado de prova existe, o provador é sempre capaz de fazer o verificador aceitar dando a ele o certificado. No caso onde não há certificado de prova válido, contudo, a entrada não está na linguagem, e nenhum provador, por mais malicioso que seja, pode convencer o verificador do caso contrário, porque qualquer certificado de prova será rejeitado.

Protocolos de Arthur–Merlin e Merlin–Arthur

[editar | editar código-fonte]

Embora NP pareça usar interação, ela não usava até que em 1985 o conceito de computação com interação foi concebido por dois grupos de pesquisas independentes. Uma abordagem, por László Babai, que publicou "Trading group theory for randomness",[1] definiu a hierarquia de classe Arthur-Merlin (AM). Nessa apresentação, Arthur (o verificador) é uma máquina probabilística de tempo polinomial, enquanto Merlin (o provador) tem recursos ilimitados.

A classe MA em particular é uma simples generalização da interação de NP acima em que o verificador é probabilístico em vez de determinístico. Também, em vez de requerer que o verificador sempre aceite certificados válidos e rejeite certificados inválidos, o seguinte é mais brando:

  • Completude: se a cadeia é uma linguagem, o provador deve ser capaz de dar um certificado tal que o verificador irá aceitar com probabilidade no mínimo 2/3 (dependendo das escolhas randômicas do verficador).
  • Corretude: se a cadeia não está na linguagem, nenhum provador, ainda que malicioso, irá ser capaz de convencer o verificador de aceitar a cadeia com probabilidade excedendo 1/3.

Essa máquina é potencialmente mais poderosa que um protocolo NP interativo ordinário e os certificados não são menos práticos de verificar, uma vez que algoritmos BPP são considerados como abstrações de computação prática/real (ver BPP).

Moedas públicas versus moedas privadas

[editar | editar código-fonte]

Na mesma conferência onde Babai definiu seu sistema de prova para MA, Shafrira Goldwasser, Silvio Micali e Charles Rackoff[2] publicaram um artigo definindo o sistema de prova interativa IP[f(n)]. Esse tem as mesmas máquinas como o protocolo MA, exceto que f(n) rodadas são permitidas para uma entrada de tamanho n. Em cada rodada, o verificador executa o cálculo e passa uma mensagem para o provador, e o provador executa o cálculo e passa informação de volta para o verificador. No fim, o verificador precisa tomar sua decisão. Por exemplo, em um protocolo IP[3], a sequência deveria ser VPVPVPV, onde V é a vez do verificador e P é a vez do provador.

Nos protocolos de Arthur-Merlin, Babai definiu uma classe similar AM[f(n)] que permitiu f(n) rodadas, mas ele colocou uma condição extra na máquina: o verificador deve mostrar ao provador todos os bits aleatórios que ele usa na sua computação. O resultado é que o verificador não pode "esconder" nada do provedor, porque o provedor é poderoso o suficiente para simular qualquer coisa que o verificador faz se ele sabe quais bits aleatórios o verificador usou. Isso é chamado de protocolo moeda pública, pois os bits aleatórios ("cara ou coroa") são visíveis para ambas as máquinas. A abordagem IP é chamada de protocolo moeda privada por contraste.

O problema essencial com moedas públicas é que se o provador deseja maliciosamente convencer o verificador a aceitar uma cadeia que não está na linguagem, parece que o verificador pode ser capaz de frustrar seus planos se ele consegue esconder seu estado interno do mesmo. Esta foi a primeira motivação na definição dos sistemas de prova IP.

Em 1986, Goldwasser e Sipser[3] mostraram, talvez surpreendentemente, que a habilidade do verificador de esconder o cara ou coroa das moedas do provador torna isso um pouco melhor depois de tudo, em que um protocolo Arthur-Merlin de moeda pública com somente mais duas rodadas pode reconhecer todas as mesmas linguagens. O resultado é que protocolos de moeda pública e moeda privada são grosseiramente equivalentes. De fato, como Babai mostrou em 1988, AM[k]=AM para toda constante k, portanto o IP[k] não tem vantagem sobre AM.[4]

Para demonstrar o poder dessas classes, considere o problema do isomorfismo de grafos, o problema de determinar se é possível permutar os vértices de um grafo de modo que ele seja idêntico ao outro grafo. Este problema está em NP, de modo que o certificado de prova é uma permutação que faz os grafos iguais. Acontece que o complemento do problema de isomorfismo de grafos, um problema co-NP não se sabe estar em NP, tem um algoritmo AM e a melhor maneira de ver isso é via algoritmo de moedas privadas.[5]

IP

[editar | editar código-fonte]

Moedas privadas podem não ser úteis, mas mais rodadas de interação são úteis. Se nós permitimos a máquina verificadora probabilística e o todo-poderoso provador interagir por um número polinomial de rodadas, nós pegamos a classe de problemas chamada IP. Em 1992, Adi Shamir revelou em um dos resultados centrais da teoria da complexidade que IP é igual a PSPACE, a classe de problemas solúveis por uma Máquina de Turing determinística em espaço polinomial.[6]

QIP

[editar | editar código-fonte]

Se nós permitimos os elementos do sistema usar computação quântica, o sistema é chamado um sistema de prova interativa quântico, e a classe de complexidade correspondente é QIP.[7] A series of recent results culminating in a paper published in 2010 is believed to have demonstrated that QIP = PSPACE.[8][9]

Conhecimento zero

[editar | editar código-fonte]
Ver artigo principal: Provas de conhecimento-zero

Sistemas de provas interativas não conseguem somente resolver problemas que acredita-se não estarem em NP, mas sob suposições sobre a existência de funções de mão única, um provador pode convencer o verificador da solução sem nunca dar a informação do verificador sobre a solução. Isso é importante quando o verificador não pode ser confiável com a solução completa. No primeiro momento parece impossível que o verificador possa ser convencido que há uma solução quando o verificador não viu o certificado, mas estas provas, conhecidas como provas de conhecimento-zero pensa-se que de fato existem para todos os problemas em NP por by Goldwasser, Micali e Rackoff, mas a extensão do seu poder foi mostrado por Oded Goldreich, Silvio Micali e Avi Wigderson.[5]

MIP

[editar | editar código-fonte]

Um objetivo dos projetistas de IP foi criar o mais poderoso sistema de prova interativa e no princípio isso parecia como que ele não poderia ser feito mais poderoso sem fazer o verificador mais poderoso e portanto impraticável. Goldwasser et al. superaram isso em 1988 "Multi prover interactive proofs: How to remove intractability assumptions", que define uma variante de IP chamada MIP em cuja há dois provadores independentes.[10] Os dois provadores não podem se comunicar uma vez que o verificador tenha começado a enviar mensagens para eles. Assim como é mais fácil de dizer se um criminoso está mentindo, se ele e seu parceiro são interrogados em salas separadas, é consideravelmente mais fácil de detectar um provador malicioso que tenta enganar o verificador em aceitar uma cadeia que não está na linguagem se há outro provador que pode fazer uma dupla checagem.

De fato, isso é tão útil que Babai, Fortnow, e Lund foram capazes de mostrar que MIP = NEXPTIME, a classe de todos os problemas solúveis por uma Máquina de Turing não determinística em tempo exponencial, uma classe muito grande.[11] NEXPTIME contém PSPACE e acredita-se que rigorosamente contém PSPACE. Adicionando um número constante de provedores adicionais além de dois não potencializa o reconhecimento de mais linguagens. Este resultado abriu caminho para o célebre Teorema PCP, que pode ser considerado uma versão "em escala menor" deste teorema.

MIP também tem a útil propriedade que provas de conhecimento-zero para qualquer linguagem em NP podem ser descritas sem a suposição de funções mão única que IP deve fazer. Isso tem relação com o projeto de algoritmos criptográficos comprovadamente inquebráveis​​.[10] Mais ainda, um protocolo MIP pode reconhecer todas as linguagens em IP em somente um número constante de rodadas, e se um terceiro provador é adicionado, ele pode reconhecer todas as linguagens em NEXPTIME em um número constante de rodadas, mostrando novamente seu poder sobre IP.

PCP

[editar | editar código-fonte]
Ver artigo principal: Provas verificáveis probabilisticamente

Enquanto os projetistas de IP consideraram generalizações dos sistemas de provas interativas de Babai, outros consideraram restrições. Um sistema de prova interativa muito útil é PCP(f(n), g(n)), que é uma restrição de MA onde Arthur pode somente usar f(n) bits aleatórios e somente examinar g(n) bits do certificado de prova enviado por Merlin (essencialmente usando acesso aleatório).

Há um número de resultados fáceis de provar sobre várias classes PCP. PCP(0, poli), a classe de máquinas de tempo polinomial sem aleatoriedade mas acesso para um certificado, é apenas NP. PCP(poli, 0), a classe de máquinas de tempo polinomial com acesso polinomial a vários bits aleatórios é co-RP. O primeiro grande resultado de Arora e Safra foi que PCP(log, log) = NP; dito de outra forma, se o verificador no protocolo NP é forçado a escolher somente O(log n) bits do certificado de prova para olhar, isso não fará nenhuma diferença, desde que tenha O('log n' ') bits aleatórios para usar.[12]

Além disso, o Teorema PCP afirma que o número de acessos de prova pode ser trazido para baixo até chegar a uma constante. Isto é, NP = PCP(log, O(1)).[13] Eles usaram essa caracterização valiosa de NP para provar que algoritmos de aproximação não existem para as versões de otimização de determinados problemas NP-completos a menos que P = NP. Tais problemas estão sendo estudados no campo conhecido como dificuldade de aproximação.

Ver também

[editar | editar código-fonte]

Referências

  1. ↑ László Babai. Trading group theory for randomness. Proceedings of the Seventeenth Annual Symposium on the Theory of Computing, ACM. 1985.
  2. ↑ Goldwasser, S.; Micali, S.; Rackoff, C. (1989). «The knowledge complexity of interactive proof systems» (PDF). Philadelphia: Society for Industrial and Applied Mathematics. SIAM Journal on Computing. 18 (1): 186–208. ISSN 1095-7111. doi:10.1137/0218012  Extended abstract
  3. ↑ Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. Proceedings of ACM STOC'86, pp. 58–68. 1986.
  4. ↑ László Babai and Shlomo Moran. Arthur–Merlin games: a randomized proof system, and a hierarchy of complexity classes. Journal of Computer and System Sciences, 36: p.254–276. 1988.
  5. ↑ a b O. Goldreich, S. Micali, A. Wigderson. Proofs that yield nothing but their validity. Journal of the ACM, volume 38, issue 3, p.690–728. July 1991.
  6. ↑ Adi Shamir. IP = PSPACE. Journal of the ACM, volume 39, issue 4, p.869–877. October 1992.
  7. ↑ Tsuyoshi Ito; Hirotada Kobayashi; John Watrous (2010). «Quantum interactive proofs with weak error bounds». arXiv:1012.4427v2Acessível livremente [quant-ph] 
  8. ↑ Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John (2010). «QIP = PSPACE». STOC '10: Proceedings of the 42nd ACM symposium on Theory of computing. [S.l.]: ACM. pp. 573–582. ISBN 978-1-4503-0050-6 
  9. ↑ Aaronson, Scott (1 de dezembro de 2010). «QIP = PSPACE Breakthrough: Technical Perspective». Commun. ACM. 53 (12): 101–101. ISSN 0001-0782. doi:10.1145/1859204.1859230 
  10. ↑ a b M. Ben-or, Shafi Goldwasser, J. Kilian, and A. Wigderson. Multi prover interactive proofs: How to remove intractability assumptions. Proceedings of the 20th ACM Symposium on Theory of Computing, pp. 113–121. 1988.
  11. ↑ László Babai; L. Fortnow; C. Lund (1991). «Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity» (em inglês). pp. 3–40. Arquivado do original em 8 de fevereiro de 2007 
  12. ↑ Sanjeev Arora and Shmuel Safra. Probabilistic Checking of Proofs: A New Characterization of NP. Journal of the ACM, volume 45, issue 1, pp. 70–122. January 1998.
  13. ↑ Sanjeev Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof Verification and the Hardness of Approximation Problems. Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pp. 13–22. 1992.

Livros texto

[editar | editar código-fonte]

Ligações externas

[editar | editar código-fonte]
Obtida de "https://pt.wikipedia.org/w/index.php?title=Sistema_de_prova_interativa&oldid=67335888"