|
Sistema de prova interativaNa 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:
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. NPA 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 é:
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–ArthurEmbora 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:
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 privadasNa 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] IPMoedas 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] QIPSe 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 Ver artigo principal: Provas de conhecimento-zeroSistemas 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] MIPUm 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. PCPVer artigo principal: Provas verificáveis probabilisticamenteEnquanto 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émReferências
Livros texto
Ligações externas
|
