Computação Aleatória e Interativa

Permitir que algoritmos lancem moedas ou se engajem em um diálogo com um provador poderoso, mas não confiável, produz classes de complexidade como BPP e IP que remodelam nossa compreensão do que a verificação eficiente pode alcançar.

Definition

A computação aleatória aumenta uma máquina com acesso a bits aleatórios e mede a probabilidade de uma resposta correta, enquanto a computação interativa permite que um verificador de tempo polinomial troque mensagens com um provador; as classes resultantes capturam problemas solucionáveis com erro limitado ou verificáveis por meio de interação.

Scope

Este tópico abrange classes de complexidade probabilística, incluindo BPP, RP e ZPP, e a questão de saber se a aleatoriedade pode ser eliminada, sistemas de prova interativos e o teorema que identifica IP com PSPACE, provas de conhecimento zero e provas verificáveis probabilisticamente que fundamentam a dificuldade da aproximação.

Core questions

• O acesso à aleatoriedade permite que os algoritmos resolvam mais problemas de forma eficiente?
• Um verificador limitado pode verificar afirmações feitas por um provador poderoso e não confiável?
• Como se pode ser convencido de que uma afirmação é verdadeira sem aprender mais nada?
• Como a verificação de prova interativa e probabilística restringe a aproximação?

Key theories

IP é igual a PSPACE

As linguagens prováveis por um protocolo interativo entre um verificador de tempo polinomial e um provador todo-poderoso são exatamente aquelas decidíveis em espaço polinomial, uma medida impressionante do poder da interação.

O teorema PCP

Todo problema em NP tem provas que podem ser verificadas lendo apenas um número constante de bits escolhidos aleatoriamente, um resultado que define o limiar preciso além do qual a aproximação de muitos problemas de otimização é NP-difícil.

Clinical relevance

Essas ideias têm impacto tecnológico direto: provas de conhecimento zero permitem autenticação e protocolos de preservação de privacidade e sustentam a computação verificável em blockchains, enquanto provas verificáveis probabilisticamente explicam por que muitos problemas de otimização não podem ser eficientemente aproximados, orientando onde os algoritmos de aproximação podem e não podem ter sucesso.

History

Provas interativas e de conhecimento zero foram introduzidas por Goldwasser, Micali e Rackoff e por Babai em meados da década de 1980. Shamir provou que IP é igual a PSPACE em 1990, e o teorema PCP, completado por Arora e outros no início da década de 1990, revolucionou o estudo da aproximação, enquanto a conjectura de que o tempo polinomial aleatório é igual ao tempo polinomial determinístico permanece em aberto.

Debates

A aleatoriedade adiciona poder computacional genuíno?

Muitos resultados sugerem que BPP é igual a P sob suposições plausíveis de dificuldade, o que significa que a aleatoriedade poderia, em princípio, ser removida de algoritmos eficientes. Se essa desaleatorização se mantém incondicionalmente é algo não resolvido, deixando em aberto o quão essencial a aleatoriedade realmente é.

Key figures

• Shafi Goldwasser
• Silvio Micali
• László Babai
• Adi Shamir

Seminal works

• aroraBarak2009
• goldreich2008

Frequently asked questions

Como o lançamento de moedas pode ajudar um algoritmo?

A aleatoriedade permite que um algoritmo evite entradas de pior caso, fazendo escolhas que o adversário não pode prever, muitas vezes produzindo procedimentos mais simples ou mais rápidos, como no teste de primalidade. A classe BPP de erro limitado captura problemas solucionáveis dessa forma com uma pequena e controlável chance de erro.

O que é uma prova de conhecimento zero?

É um protocolo interativo que convence um verificador de que uma afirmação é verdadeira sem revelar nada além de sua verdade, nem mesmo por que ela se mantém. Tais provas permitem, por exemplo, provar que você sabe uma senha ou segredo sem divulgá-lo, e são fundamentais para a privacidade criptográfica moderna.