Paysage des systèmes de preuve interactifs

Ma première question est de savoir si une caractérisation de système de preuve interactive est connue pour toutes les classes de complexité classiques. J'appellerais P, NP, PSPACE, EXP, NEXP, EXPSPACE, les fonctions récursives et récursivement énumérables (entre autres). Plus précisément, une caractérisation de système de preuve interactive est-elle connue pour les fonctions récursives et récursivement énumérables?

Je sais seulement que IP = PSPACE et que MIP = NEXPTIME. Par «savoir», je comprends les définitions des objets des deux côtés de l'égalité et éventuellement de l'égalité.

Ma deuxième question est de savoir s'il existe un résumé graphique des différents types de systèmes de preuve interactifs et des classes de complexité qu'ils caractérisent.

Plus précisément, je voudrais une référence à une figure similaire à l'image d'Immerman des caractérisations de complexité de description .

Vous pouvez trouver de nombreuses caractérisations (en particulier sur les vérificateurs délimités par l'espace) dans la célèbre enquête de Condon: La complexité des systèmes de preuve interactifs délimités par l'espace .

En voici une liste:

• , où 2pfa (le vérificateur) est un automate fini probabiliste à deux voies.$\mathsf{RE} = \mathsf{weak\mbox{-}IP(2pfa)}$

• , où pfa (le vérificateur) est un automate fini probabiliste unidirectionnel interagissant avec deux prouveurs.$\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)}$

• ,$\mathsf{P} = \mathsf{AM(log\mbox{-}space)}$ , etc.$\mathsf{EXP} = \mathsf{AM(poly\mbox{-}space)}$

Quelques résultats récents (principalement quantiques):

• parYakaryilmaz, où 2qcfa (le vérificateur) est un automate fini à deux voies ayant un registre quantique de taille constante.$\mathsf{RE} = \mathsf{weak\mbox{-}AM(2qcfa)}$

• parYakaryilmaz, où 2pca (l'ancien vérificateur) est un automate fini probabiliste à deux voies avec un compteur et 2qca (ce dernier vérificateur) est un deux -automate fini quantique à deux voies avec un compteur.$\mathsf{R} = \mathsf{IP(2pca)} = \mathsf{AM(2qca)}$

• Ito, Kobayashi et Watrous ont donné une nouvelle caractérisation d' basée sur des systèmes de preuve interactifs quantiques avec un écart doublement exponentiellement faible dans la probabilité d'acceptation entre les cas d'exhaustivité et de solidité.$\mathsf{EXP}$

• parJain, Ji, Upadhyay et Watrous, où QIP est la généralisation quantique des systèmes IP.$\mathsf{PSPACE} = \mathsf{QIP(poly\mbox{-}time)}$

• $\mathsf{NP}$

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

NP est souvent caractérisé comme un système de preuve dans lequel le prouveur envoie une preuve de longueur polynomiale à un vérificateur déterministe de temps polynomial, et après quoi il n'y a plus d'interaction. La classe des langages récursivement énumérables peut être caractérisée de la même manière en remplaçant "polynôme" par "fini".

De plus, étant donné que la classe des langages récursifs R est l'intersection de RE et coRE, vous pouvez caractériser R comme un système de preuve dans lequel un prouveur tout-puissant peut convaincre un vérificateur à temps fini à la fois dans la validité des revendications correctes et dans l'invalidité de fausses allégations.

La classe EXP a une caractérisation en termes de système de preuve avec des "prouveurs concurrents" - c'est-à-dire un système de preuve dans lequel il y a un prouveur qui essaie de convaincre le vérificateur que la réclamation est vraie et un réfuteur qui essaie de convaincre le vérificateur que la réclamation est fausse. Voir l'article "Faire des jeux courts" de Feige et Kilian pour plus de détails.