MIP avec des étalons efficaces

17

Il est bien connu que l'ensemble des langages ayant des systèmes de preuve interactifs à deux prouveurs, dans lesquels le vérificateur s'exécute en temps polynomial (MIP), est NEXP. Mais existe-t-il des limites connues sur la puissance de ces preuves interactives lorsque les prouveurs sont limités en puissance? Par exemple, quelle est la classe de langages qui admettent des preuves interactives à deux provers avec des provers à temps polynomial?

Plus précisément, disons que sur une entrée x j'autorise le temps de pré-calcul arbitraire des prouveurs, mais une fois que l'interaction avec le vérificateur commence, ils sont limités à l'utilisation de l'espace polynomial (y compris le stockage des résultats de tout pré-calcul) et du temps polynomial pour calculer leurs réponses à la question du vérificateur. Supposons également que ces limites d'espace et de temps soient un polynôme fixe dans la longueur des questions qui seront envoyées par le vérificateur (au lieu de la longueur de x), afin d'exclure une solution plus triviale dans laquelle le vérificateur épuiserait en quelque sorte l'espace du proviseur limité en posant polynomialement plus de questions.

De toute évidence, cela suffit pour NP. Et PSPACE? S'il n'y avait que l'espace limité, ils pourraient le faire, mais qu'en est-il du temps? Y a-t-il des résultats intéressants dans cette direction?

Je suis également intéressé par d'autres limitations que l'on pourrait considérer sur les étalons. L'un d'entre eux serait la quantité de vérificateur de la communication, qui, je pense, a été étudiée en profondeur dans le contexte des PCP. Quelles sont les autres contraintes intéressantes?

Thomas
la source

Réponses:

17

On dirait que cette classe serait exactement MA. Le témoin pourrait être le résultat d'un prétraitement (qui est de taille polynomiale). La procédure de vérification probabiliste consisterait alors à simuler le protocole, y compris les multiples prouveurs (qui sont polynomiaux compte tenu des résultats du prétraitement).

Russell Impagliazzo

Russell Impagliazzo
la source
Bon point, merci. Plus généralement, je me demandais de quelle manière plusieurs prouveurs pourraient prouver des langues qui sont en dehors de leur temps T lié (modulo l'étape de pré-traitement), à un vérificateur poly-temps, et votre réponse montre que ce ne sera jamais plus que le correspondant MA (T), avec un vérificateur de temps T. Mais comment se compare-t-il à une classe de vérificateur poly-temps? Disons que si les prouveurs sont maintenant autorisés à être PSPACE, ils peuvent toujours prouver NEXP. Peuvent-ils être plus restreints et prouver la même chose?
Thomas
2

Si les deux prouveurs sont limités à deux machines BQP qui ne communiquent pas entre elles, mais partagent un enchevêtrement, tandis que le vérificateur est en BPP, alors les deux prouveurs peuvent prouver n'importe quel langage en BQP au vérificateur classique en utilisant le calcul quantique aveugle universel. protocole de Broadbent, Fitzsimons et Kashefi. Ce protocole a également été utilisé par les mêmes auteurs comme bloc de construction pour afficher QMIP = MIP * .

Martin Schwarz
la source
1
Merci Martin, je ne voulais pas mentionner mon propre travail.
Joe Fitzsimons