em termos de

15

O sistema de prova probabilística é comumente referido como uma restrição de , onde Arthur pode usar apenas bits aleatórios e apenas examinar g (n) bits do certificado de prova enviado por Merlin (consulte http://en.wikipedia.org/wiki/Interactive_proof_system#PCP ).PCP[f(n),g(n)]MAf(n)g(n)

No entanto, em 1990, Babai, Fortnow e Lund provaram que PCP[poly(n),poly(n)]=NEXP , portanto não é exatamente uma restrição. Quais são os parâmetros ( f(n),g(n) ) para os quais PCP[f(n),g(n)]=MA ?

Belle
fonte

Respostas:

18

Se você deseja redefinir a definição de MA em termos de PCP, precisa de outro parâmetro para PCP, ou seja, o comprimento da prova. MA é claramente o mesmo que PCP com aleatoriedade polinomial, consultas polinomiais e provas de comprimento polinomial. Normalmente, o comprimento da prova no PCP não é restrito (isto é, é limitado apenas implicitamente por aleatoriedade e consultas), mas isso é insuficiente para redefinir a definição de MA.

Se você está procurando alguma caracterização do formato MA = PCP ( q ( n ), r ( n )), que não é apenas a reformulação da definição de MA, não creio que essa caracterização seja conhecida.

Tsuyoshi Ito
fonte
11

Tsuyoshi Ito respondeu a pergunta literalmente, mas queria comentar sobre a semântica do MA e do PCP e como elas diferem.

MA é a versão probabilística do NP, ou seja, o verificador também pode usar vários bits aleatórios.

No PCP, podemos nos referir à "aleatoriedade" do verificador, mas geralmente a aleatoriedade é logarítmica no tempo de execução do verificador, ou seja, o verificador poderia ter tentado todas as seqüências aleatórias possíveis por si só. Em outras palavras, essa "aleatoriedade" não comprará ao verificador qualquer poder computacional, diferentemente do caso do MA.

[Então, para que serve essa "aleatoriedade"? O objetivo do PCP é que, para verificação probabilística, basta um único teste - com um número constante de consultas à prova -]

Adendo (seguindo o comentário de Tsuyoshi): Nas caracterizações de NP por PCP, o tempo de execução do verificador pode ser policlarítmico e, da mesma forma, nas caracterizações de NEXP, o tempo de execução do verificador é polinomial. No entanto, a aleatoriedade nas construções de PCP é tipicamente usada apenas para escolher um teste (nas caracterizações de NP, dentre vários testes polinucleares, e nas caracterizações de NEXP, entre muitos exponencialmente) e não para ajudar no cálculo. Além disso, em MA, a prova é de tamanho polinomial, enquanto nas caracterizações de NEXP, a prova é de tamanho exponencial.

Dana Moshkovitz
fonte
Concordo que damos ao verificador apenas aleatoriedade logarítmica no teorema do PCP para NP, de modo que essa aleatoriedade sozinha não comprará ao verificador qualquer poder computacional. No entanto, parece que você está fazendo uma afirmação mais geral do que essa afirmando que "geralmente a aleatoriedade é logarítmica no tempo de execução do verificador", o que, receio, é geral demais para ser verdade. Normalmente, não permitimos que o verificador gaste tempo exponencial, mesmo quando consideramos PCP (poly, poly) = NEXP (embora isso não mude essa igualdade), e isso parece ser um contra-exemplo para sua declaração.
Tsuyoshi Ito
1
Obrigado pelo seguimento! Eu acho que agora entendo melhor o que você quer dizer com dizer que MA e PCP usam a aleatoriedade de maneira diferente.
Tsuyoshi Ito