Beigi, Shor e Watrous têm um excelente artigo sobre o poder das provas interativas quânticas com mensagens curtas. Eles consideram três variantes de 'mensagens curtas', e a que mais me interessa é a segunda variante em que qualquer número de mensagens pode ser enviado, mas o tamanho total da mensagem deve ser logarítmico. Em particular, eles mostram que esses sistemas interativos de prova têm o poder expressivo do BQP.
O que eu quero saber é se há resultados análogos para a configuração de múltiplos provadores, seja para verificadores clássicos ou quânticos. Existem resultados de complexidade não triviais conhecidos para provas interativas com vários provadores em que o comprimento total de todas as mensagens é restrito como logarítmico no tamanho do problema?
fonte
Respostas:
Caso completamente clássico (MIP)
Se o verificador é clássico e não há emaranhamento prévio entre os provadores, sua classe contém BPP∪NP e está contida em MA .
É trivial que o BPP seja um limite inferior. Para mostrar que a classe contém NP, considere o sistema de prova interativa padrão de dois provadores e uma rodada para obter 3 cores, com perfeito erro de integridade e solidez 1-1 / poli. Se você deseja reduzir o erro de solidez a uma constante, combine isso com o teorema do PCP.
Quanto ao limite superior, a seguinte declaração mais forte é válida: MIP com a restrição de que o comprimento total da mensagem do verificador para cada provador seja O (log n ) é igual a MA. Isso ocorre porque a estratégia de cada provador pode ser descrita por uma cadeia de comprimento polinomial.
Curiosamente, existe outro limite superior quando o sistema possui perfeição completa. Nomeadamente, os sistemas interativos de prova com vários provedores, com perfeita perfeição com comunicação total de O (log n ) bits, reconhecem no máximo P NP [log] , e isso vale mesmo se permitirmos erro de solidez ilimitado. Para provar isso, no caso de dois provadores, vamos x s ser a concatenação de todas as respostas dadas pelo primeiro provador quando a concatenação de todas as questões para o primeiro provador é s , e definir y t analogamente para a segunda provador. Para serem aceitas pelo verificador com certeza, essas variáveis x s e y tdeve satisfazer certas restrições e observe que este é um 2CSP. Existem no máximo opções poli ( n ) para tuplas ( s , t , x s , y t ) e, para cada escolha, podemos usar o oracle NP para testar se o verificador rejeita essa tupla. Portanto, com o NP oracle, podemos listar todas as restrições nas variáveis x s e y tem tempo polinomial. Finalmente, usamos o oracle NP mais uma vez para testar se existe uma atribuição para essas variáveis que satisfaça todas as restrições. Embora esse algoritmo use o oracle NP polinomialmente muitas vezes, todas as consultas, exceto a última, podem ser feitas em paralelo e, portanto, isso pode ser convertido em um algoritmo P NP [log] . O caso de mais de dois provadores é análogo.
Esse limite superior implica que, embora todo sistema MA possa ser transformado em um com perfeita perfeição, não podemos esperar um sistema de prova interativa com vários provadores com perfeita perfeição com comunicação com O (log n ) bits, a menos que MA⊆P NP [log] . Não sei o quão improvável é a inclusão MA⊆P NP [log] , mas apenas observo que a Zoologia da Complexidade afirma que existe um oráculo em relação ao qual BPP⊈ P NP (e, portanto, claramente MA⊈P NP [log] ).
(No caso de um único provador, o Teorema 2 de Goldreich e Håstad [GH98] implica que o IP com o comprimento total da mensagem O (log n ) bits seja igual ao BPP.)
Adicionado . Uma caracterização necessária e suficiente é a seguinte.
Para explicar essa caracterização, precisamos de uma variante da noção de redutibilidade de Karp (redutibilidade polinomial em muitos um). Para dois problemas de decisão A e B , digamos que A seja FP- BPP- redutível a B (eu sei, esse é um nome horrível) quando houver uma máquina de Turing determinística M em tempo polinomial com acesso ao oráculo BPP que mapeia sim- instâncias para instâncias sim e não instâncias para não instâncias, nas quais permitimos acesso oracle “não inteligente” (o que significa que Mpode fazer uma consulta ao BPP oracle sobre uma instância que não satisfaz a promessa do problema do BPP; nesse caso, o oracle retorna sim ou não arbitrariamente). Então, pode-se provar que as seguintes condições em um problema A são equivalentes.
(i) A possui um sistema de prova interativa de múltiplos provedores com comunicação de O (log n ) bits e erro delimitado nos dois lados.
(ii) A possui um sistema de prova interativa de dois provadores, com comunicação de O (log n ) bits, erro de completude exponencialmente pequeno e erro de sonoridade constante.
(iii) A é FP BPP- redutível a um problema no NP.
(Ideia de prova: a implicação (ii) ⇒ (i) é trivial. A implicação (i) ⇒ (iii) pode ser obtida de maneira semelhante à prova acima no caso de erro unilateral. Implicação (iii) ⇒ (ii) ) segue o teorema do PCP porque a classe de problemas que satisfazem a condição (ii) é encerrada na redutibilidade do FP BPP .)
Verificador clássico com provadores emaranhados (PIM *)
Em seguida, considere o caso com um verificador clássico e provadores emaranhados. Nesse caso, a classe com erro limitado novamente contém BPP∪NP.
Kempe, Kobayashi, Matsumoto, Toner e Vidick [KKMTV11] mostram que todos os problemas no NP têm um sistema de prova interativa de três provadores com um erro de perfeição e solidez perfeito 1-1 / poli, onde o comprimento total das mensagens é O ( log n ) bits, e a solidez se mantém contra provadores emaranhados. Portanto, o MIP * com o comprimento total da mensagem O (log n ) bits e o erro limitado contém NP. Um resultado posterior de Ito, Kobayashi e Matsumoto [IKM09] (plugue descarado) reduz o número de provadores de três para dois. O caso de solidez constante está aberto no topo do meu conhecimento.
Não se sabe se MIP * com comprimento total de mensagem O (log n ) bits está contido na classe R de problemas decidíveis ou não, e essa pergunta é equivalente a se MIP * ⊆R (outro problema em aberto) pelo argumento de preenchimento.
Referências
[GH98] Oded Goldreich e Johan Håstad. Sobre a complexidade de provas interativas com comunicação limitada. Information Processing Letters , 67 (4): 205-214, agosto de 1998. http://dx.doi.org/10.1016/S0020-0190%2898%2900116-1
[IKM09] Tsuyoshi Ito, Hirotada Kobayashi e Keiji Matsumoto. Oracularização e provas interativas completas de dois provadores contra estratégias não locais. Anais: Vigésima Quarta Conferência Anual do IEEE sobre Complexidade Computacional (CCC 2009) , 217–228, julho de 2009. http://dx.doi.org/10.1109/CCC.2009.22
[KKMTV11] Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner e Thomas Vidick. Jogos complicados são difíceis de aproximar. SIAM Journal on Computing , 40 (3): 848–877, 2011. http://dx.doi.org/10.1137/090751293
fonte