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?
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 * .
la source