Provas interativas para níveis da hierarquia polinomial

33

Sabemos que, se você possui uma máquina PSPACE, ela é poderosa o suficiente para fornecer uma prova interativa de qualquer nível da hierarquia polinomial. (E se bem me lembro, tudo o que você precisa é #P.) Mas suponha que você queira fornecer uma prova interativa de associação em um idioma. É suficiente ser capaz de resolver problemas em ? A solução de problemas em adequada? De modo mais geral, se você pode resolver ou problemas, pelo que isto é suficiente para gerar provas interativas de todos os languates em ? $\Sigma_2$ $\Sigma_2$ $\Sigma_5$ $\Sigma_k$ $\Pi_k$ $\Sigma_\ell$ $\Sigma_\ell$

Essa questão foi inspirada nessa questão de troca de pilha de história .

cc.complexity-theory interactive-proofs Peter Shor
fonte

Você está interessado apenas no caso de um único provador ou no caso de vários provadores? Parece-me que a maneira óbvia de atacar isso seria por meio de PCPs, o que pode ser direto para dois provadores, mas provavelmente não funcionará para um único provador.

Joe Fitzsimons

1

Eu estaria interessado nos dois casos. Eu me pergunto sobre essa questão para provadores únicos há um bom tempo, mas não havia pensado em vários provadores.

Peter Shor

4

@ Peter: Examinando o documento IP = PSPACE, parece que a prova passaria pelo

(que é completo para

) em vez do QBF, desde que você tenha um comprovador suficientemente poderoso para calcular as identidades polinomiais decorrentes de a aritmitização do

. Estou esquecendo de algo?

{QBF}_{k}

$\mbox{QBF}_k$

Σ_{k}^{P}

$\Sigma^P_k$

{QBF}_{k}

$\mbox{QBF}_k$

Joe Fitzsimons

1

@ Joe, eu não considerei essa idéia; Pode funcionar.

quer

2

Joe, talvez você deve publicá-la como uma resposta

Suresh Venkat

25

Mesmo para fornecer um IP para o coNP, usando as técnicas atuais, é preciso aritmetizar, ou seja, usar a contagem, o que significa essencialmente toda a potência do #P. Qualquer provador mais fraco, mesmo para o coNP, seria muito interessante, eu acho (em particular, implicaria uma nova técnica não relativística).

Noam
fonte

@ Peter: Noam está certo. Cito as seguintes linhas a partir daqui : ... basear o hash resistente à colisão na dureza da pior das hipóteses de NP através de uma redução de caixa preta implica um sistema interativo de prova para co-NP com o provador em BPP ^ NP ... Todos os conhecidos (mesmo multi-provador) sistemas de prova de co-NP necessitam de provadores com a complexidade #P ...

MS Dousti

Nesse caso, minha resposta provavelmente não faz sentido. Obrigado por apontar isso.

Joe Fitzsimons

Na verdade, isso é realmente interessante, dado que uma prova interativa para o não-isomorfismo de Graph precisa apenas de um provador com um oráculo para esse problema. Parece uma evidência de que o IG é muito, muito fraco (como em P), ou os limites para provas interativas dos níveis da hierarquia polinomial provavelmente são muito frouxos.

Joe Fitzsimons

1

Presumo que vários provadores não são conhecidos por ajudar. Isso está correto?

quer

1

@ Joe A prova para não isomorfismo gráfico é uma moeda redonda pública prova constante, colocando-o assim na classe AM (acredita-se ser igual NP, e, portanto, GI e RNB são acreditados para ser em

). Isso é muito menor do que a prova redonda polinomial que se acredita ser necessária para provar a participação em problemas completos da coNP.

N P \cap c o N P

$NP \cap coNP$

precisa

21

Este é um problema aberto conhecido (maravilhoso) em que trabalhei de tempos em tempos sem sucesso.

Avi Wigderson e eu mencionamos o problema em nosso trabalho de algebrização , onde levantamos a questão de saber se contenções como coNP ⊆ IP _NP podem ou não ser provadas por meio de técnicas de algebrização. (Aqui IP _NP denota IP com um verificador BPP e um provador BPP ^NP .) Se (como eu conjecturo) a resposta for não, isso forneceria uma razão formal pela qual qualquer protocolo interativo como o que Peter solicita exigiria não relativizar técnicas que vão "fundamentalmente além" daquelas usadas para IP = PSPACE.

Uma pergunta análoga é se BQP = IP _BQP , onde IP _BQP significa IP com um verificador BPP e um provador BQP (tempo polinomial quântico). Essa questão também está em aberto - embora um avanço recente de Broadbent, Fitzsimons e Kashefi tenha mostrado que uma afirmação intimamente relacionada é verdadeira.

Scott Aaronson
fonte

20

Sim, a questão de saber se o coNP tem uma prova interativa em que o provador é mais fraco que o #P (digamos, polytime com acesso ao NP oracle) é uma questão em aberto bem conhecida. O artigo recente de Haitner, Mahmoody e Xiao a seguir discute essa questão e mostra algumas conseqüências da suposição de que isso não pode ser feito.

Boaz Barak
fonte

11

Como Suresh sugeriu que eu postasse meu comentário como resposta, eu o farei. No entanto, não considero que isso constitua uma resposta completa, pois não tentei provar isso, e pode ser um beco sem saída.

A prova IP = PSPACE original funciona produzindo uma prova interativa para o QBF . Um caso restrito de QBF, está completo para . A mesma estratégia de aritmetização funcionará igualmente bem para o . A parte computacionalmente difícil da estratégia dos provadores parece estar reduzindo o grau dos polinômios envolvidos e avaliando as fórmulas QBF que surgem. Parece provável que isso possa ser alcançado usando um oráculo para o nível correspondente da hierarquia polinomial ( ), refazendo a aritmitização em cada rodada, uma vez que o verificador tenha fornecido suas escolhas aleatórias. $\mbox{QBF}_k$ $\Sigma^P_k$ $\mbox{QBF}_k$ $\Sigma^P_k$

Joe Fitzsimons
fonte

a questão já surge na prova do coNP. O protocolo de verificação geral possui n rodadas (uma para cada variável). Em cada rodada, o provador precisa apresentar os coeficientes do polinômio que são obtidos por uma soma exponencialmente grande. Não sei como fazê-lo usando menos energia do que #P.

precisa

@ Boo: Sim, acho que essa abordagem está destinada ao fracasso. Eu pensei que tinha visto uma versão da aritmetização feita em algum lugar de tal maneira que o polinômio assumisse apenas os valores 1 ou 0 para entradas de 0s e 1s. Se for esse o caso, parece que você poderia usar um oráculo para um problema de decisão correspondente. Então, novamente, eu posso apenas ter imaginado isso!

Joe Fitzsimons

Provas interativas para níveis da hierarquia polinomial

Respostas: