Paisagem de sistemas interativos de prova

Minha primeira pergunta é se uma caracterização interativa de sistema de prova é conhecida por todas as classes clássicas de complexidade. Eu chamaria funções clássicas de P, NP, PSPACE, EXP, NEXP, EXPSPACE, recursivas e recursivamente enumeráveis ​​(entre outras). Especificamente, uma caracterização do sistema de prova interativa é conhecida por funções recursivas e recursivamente enumeráveis?

Eu só sei que IP = PSPACE e que MIP = NEXPTIME. Por "saber", eu entendo as definições de objetos nos dois lados da igualdade e, possivelmente, entendo a igualdade.

Minha segunda pergunta é se existe um resumo gráfico de diferentes tipos de sistemas de prova interativos e as classes de complexidade que eles caracterizam.

Especificamente, gostaria de fazer referência a uma figura semelhante à imagem de Immerman das caracterizações da complexidade da descrição .

Você pode encontrar muitas caracterizações (principalmente em verificadores de espaço limitado) na famosa pesquisa de Condon: A complexidade dos sistemas de prova interativa com limite de espaço .

Aqui está uma lista de alguns deles:

• , onde 2PFA (o verificador) é uma de duas vias probabilística finito autómato.$\mathsf{RE} = \mathsf{weak\mbox{-}IP(2pfa)}$

• , em que pfa (o verificador) é um autômato finito probabilístico unidirecional que interage com dois provadores.$\mathsf{R} = \mathsf{2IP(pfa)}$

• .$\mathsf{NEXP} = \mathsf{2IP(pfa,poly\mbox{-}time)}$

• .$\mathsf{PSPACE} = \mathsf{IP(log\mbox{-}space,poly\mbox{-}time)}$

• .$\mathsf{NP} = \mathsf{oneway\mbox{-}IP(log\mbox{-}space,poly\mbox{-}time)} = \mathsf{oneway\mbox{-}IP(log\mbox{-}space,log\mbox{-}random\mbox{-}bits)}$

• , E X P = A M ( p o l y - s p a c e ) e etc.$\mathsf{P} = \mathsf{AM(log\mbox{-}space)}$$\mathsf{EXP} = \mathsf{AM(poly\mbox{-}space)}$

Alguns resultados recentes (principalmente quânticos):

• porYakaryilmaz, onde 2qcfa (o verificador) é um autómato finito de duas vias que tem um registo do quantum constante de tamanho.$\mathsf{RE} = \mathsf{weak\mbox{-}AM(2qcfa)}$

• porYakaryilmaz, onde 2pca (o antigo verificador) é um autômato finito probabilístico bidirecional com um contador e 2qca (o último verificador) é dois autômato finito quântico com um contador.$\mathsf{R} = \mathsf{IP(2pca)} = \mathsf{AM(2qca)}$

• Ito, Kobayashi e Watrous deram uma nova caracterização de base em sistemas de provas interativas quânticas com uma diferença dupla exponencialmente pequena na probabilidade de aceitação entre os casos de integridade e solidez.$\mathsf{EXP}$

• porJain, Ji, Upadhyay e Watrous, onde QIP é a generalização quântica de sistemas IP.$\mathsf{PSPACE} = \mathsf{QIP(poly\mbox{-}time)}$

• é a classe de idiomas para os quais a associação possui uma prova quântica de tamanho logarítmico com perfeição e perfeição perfeitas, que é polinomialmente próxima de 1 em um contexto em que o verificador recebe uma prova com duas partes não emaranhadas (Blier e Tapp).$\mathsf{NP}$

• $\mathsf{NL} = \mathsf{weak\mbox{-}oneway\mbox{-}IP(2pfa,constant\mbox{-}random\mbox{-}bits)}$

NP é geralmente caracterizado como um sistema de prova no qual o provador envia uma prova de comprimento polinomial a um verificador de tempo polinomial determinístico e depois do qual não há interação. A classe de linguagens recursivamente enumeráveis ​​pode ser caracterizada de maneira semelhante substituindo "polinomial" por "finito".

Além disso, como a classe das linguagens recursivas R é a interseção de ER e coRE, você pode caracterizar R como um sistema de prova no qual um todo-poderoso provador pode convencer um verificador de tempo finito tanto na validade das reivindicações corretas quanto na invalidez de Alegações falsas.

A classe EXP tem uma caracterização em termos de um sistema de prova com "provadores concorrentes" - ou seja, um sistema de prova no qual existe um provador que tenta convencer o verificador de que a alegação é verdadeira e um refutador que tenta convencer o verificador de que a alegação é falsa. Veja o artigo "Tornando os jogos curtos" de Feige e Kilian para mais detalhes.