Protocolo de Arthur-Merlin

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

Na área da Complexidade computacional, um protocolo Arthur–Merlin é um sistema de prova interativa no qual os lançamentos de moeda do verificador são obrigados a serem públicos. Essa noção foi introduzida por Babai (1985). Goldwasser & Sipser (1986) provaram que todas as linguagens com provas interativas de comprimento arbitrário com moedas privadas também têm provas interativas com moedas públicas.

O pressuposto básico é que Arthur é um computador padrão (ou verificador) equipado com um dispositivo gerador de números aleatórios, enquanto Merlin é efetivamente um oráculo com poder computacional infinito (também conhecido como um provador); mas Merlin não é necessariamente honesto, então Arthur deve analisar as informações fornecidas por Merlin em resposta às consultas de Arthur e decidir o problema por si só. Um problema é considerado solúvel por este protocolo se sempre que a resposta for "sim", Merlin possui algumas series de respostas tal que Arthur vai aceitar em pelo menos 2/3 das vezes, e sempre que a resposta for "não" , Arthur nunca vai aceitar em mais de 1/3 das vezes. Portanto, Arthur age como um verificador probabilístico de tempo polinomial, supondo que a ele é alocado tempo polinomial para tomar suas decisões e consultas.

MA[editar | editar código-fonte]

O mais simples desse tipo de protocolo é o protocolo 1-mensagem onde Merlin envia uma mensagem a Arthur, e então Arthur decide aceitar ou não através da execução de uma computação probabilística polinomial. (Isso é semelhante à definição baseada no verificador de NP, a única diferença é que Arthur está autorizado a usar aleatoriedade.) Merlin não tem acesso aos lançamentos de moeda de Arthur neste protocolo, uma vez que é um protocolo de mensagem única e Arthur joga suas moedas somente após receber a mensagem de Merlin. Esse protocolo é chamado MA. Informalmente, uma linguagem L está em MA se para todas palavras nessa linguagem , existe uma prova de tamanho polinomial que Merlin pode enviar a Arthur para convencê-lo a esse fato com alta probabilidade, e para todas as palavras não pertencentes à linguagem não existe prova que convença Arthur com alta probabilidade. Apesar disso, Arthur não é necessariamente um verificador BPP pois não se sabe se MA está contida na classe .[1]

Formalmente, a classe complexa MA é um conjunto de problemas de decisão que podem ser decididos em tempo polinomial por um protocolo de Arthur-Merlin onde o apenas o movimento de Merlin precede qualquer computação de Arthur. Em outras palavras, uma linguagem L está em MA se existe uma maquina de Turing determinística em tempo polinomial M e polinômios p, q tal que para cada palavra de entrada x de tamanho n = |x|,

  • se x pertence a L, então
  • se x não pertence a L, então


A segunda condição pode ser, alternativamente, escrita como

  • se x não está em L, then

Para comparar isso com a definição formal acima, z é a prova de Merlin (tal que o tamanho é limitado por um polinômio) e y é a palavra randômica que Arthur usa, em que ela também é limitada por um polinômio.

AM[editar | editar código-fonte]

A classe de complexidade AM (ou AM[2]) é o conjunto de problemas de decisão que podem ser decididos em tempo polinomial pelo protocolo de Arthur–Merlin com duas mensagens. Existe apenas um par de pergunta/resposta: Arthur joga algumas moedas aleatórias e envia o resultado de tudo sua moeda joga para Merlin, Merlin responde com uma suposta prova, e Arthur deterministicamente verifica a prova. Nesse protocolo, Arthur não é autorizado à enviar resultados de lançamentos de moeda para Merlin, e no estagio final Arthur deve decidir se aceita ou rejeita usando apenas as suas moedas aleatórias geradas anteriormente e a mensagem de Merlin.

Em outras palavras, uma linguagem L está em AM se existe uma Máquina de Turing em tempo polinomial M e polinômios p, q tal que para cada palavra de entrada x de tamanho n = |x|,

  • se x está emL, então
  • se x não está em L, então

A segunda condição pode ser reescrita como

  • se x não está em L, então

Como acima, z é a prova dado por Merlin (que possui tamanho limitado polinomialmente) e y é uma palavra randômica, que também é limitada polinomialmente.

A classe de complexidade AM[k] é o conjunto de problemas que podem ser decididos em tempo polinomial, com k perguntas e respostas. AM como definido acima é AM[2]. AM[3] faria começar com uma mensagem de Merlin para Arthur, então a mensagem de Arthur para Merlin e finalmente uma mensagem de Merlin para Arthur. A última mensagem deve sempre ser de Merlin para Arthur, já que ele nunca ajuda Arthur a mandar uma mensagem para Marlin antes de decidir sua resposta.

Propriedades[editar | editar código-fonte]

  • Ambos MA e AM permanecem iguais se as suas definições forem requisitadas para completude perfeitas, o que significa que Arthur aceita com probabilidade 1 (ao invez de 2/3) quando x está na linguagem. [2]
  • Para qualquer k ≥ 2 sendo k fixo, a classe AM[k]' é igual a AM[2]. Se k pode variar polinomialmente em relação ao tamanho da entrada, a classe AM[poly(n)] é uma classe bem mais forte, IP, que é igual a PSPACE.
  • MA é contido em AM, desde que MA[3] = AM, e Arthur pode, depois de receber um certificado de Merlin, arremessar a quantidade de moedas requeridas, enviar para Merlin, e ignorar a resposta.
  • É aberto se AM' e MA são diferentes. Sobre circuitos limitantes inferiores (similares aos que implicam que P=BPP), eles são ambos iguais a NP.
  • AM é o mesmo que a classe BP.NP ondeBP denota operador probabilístico de erro limitado. Também, ( também escrito como ExistsBPP) é um subconjunto de MA. Se MA é igual a é uma questão aberta.
  • A conversão para um protocolo de moeda privado, em que Merlin não pode prever o resultado das ações randômicas de Arthur, vai aumentar o número de iterações por no máximo 2 no caso geral. Então a versão privada de AM é igual à versão pública..
  • MA contém ambos NP e BPP. Para BPP isso é imediato, já que Arthur pode simplesmente ignorar Merlin e resolver o problema diretamente; para NP, Merlin precisa apenas que Arthur envie um certificado, que Arthur pode validade deterministicamente em tempo polinomial.
  • AmbosMA e AM estão contidos em hierarquia polinomial. Em particular, MA está contida na intersecção de of Σ2P e Π2P e AM está contido em Π2P. Ainda mais, MA está contido na subclasse SP
    2
    ,[3] uma classe de complexidade expressando "alternação simétrica". Isso é a generalização do teorema de Sipser–Lautemann.
  • AM é contido em NP/poly, a classe de problemas de decisão não-deterministicamente computáveis em tempo polinomial com um tamanho polinomial. A prova é a variação do teorema de Adleman.
  • MA é contido em PP; esse resultado é devido a Vereshchagin.
  • MA é contido em sua versão quântica, QMA.
  • AM contém o problema de decidir se dois grafos não são isomórficos. O protocolo usando moedas privadas é o seguinte e pode ser transformado em um público. Dado dois grafos G e H, Arthur randomicamente escolhe um dos dois, a partir dai ele escolhe uma permutação randômica de seus vértices, apresentando o gráfico permutado I para Merlin. Merlin precisa perguntar se o grafo I foi criado de G ou H. Se não existem grafos não isomórficos, Merlin irá ser apto para responder com total certeza (checando se I é isomórfico a G), se os grafos são isomórficos, se é possível que ambos G ou H não foram usados para criar I. Nesse caso Merlin não tem uma forma de dizer e convencer Arthur com probabilidade de no máximo 1/2, e isso pode ser amplificado para 1/4 através de repetição. Isso é um fato em uma prova de conhecimento zero.
  • Se AM contém coNP então PH = AM. Essa é uma evidência que isomorfismo de grafos são improváveis para ser NP-completo, já que isso implica um colapso da hierarquia polinomial.
  • É conhecido, assumindo ERH, que para algud o problema
Dado uma coleção multivariada de polinômios cada com coeficientes inteiros e de degrau no máximo d, eles possuem um complexo zero comum?
é em AM.[4]

Referências

  1. https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#existsbpp
  2. Para a prova, veja Rafael Pass and Jean-Baptiste Jeannin (24 de março de 2009). «Lecture 17: Arthur-Merlin games, Zero-knowledge proofs» (PDF). Consultado em 23 de junho de 2010. 
  3. Symmetric Alternation captures BPP
  4. Madhu Sudan, Algebra and Computation lecture notes [1], lecture 22

Bibliografia[editar | editar código-fonte]

Links Externos[editar | editar código-fonte]