propriétés de fermeture de IP (2pfa) et AM (2pfa)

9

IP (2pfa) et AM (2pfa) sont les classes de langues reconnues avec erreur bornée par les versions de pièces privées et publiques, respectivement, des systèmes de preuve interactifs avec des vérificateurs qui sont des automates finis probabilistes avec une tête d'entrée bidirectionnelle.

Des propriétés de fermeture de ces classes sont-elles connues?

cc.complexity-theory interactive-proofs Cem Say
la source

Réponses:

2

Vous pouvez jeter un œil à l'article suivant:

Dwork, C. et Stockmeyer, L. 1992. Vérificateurs d'état fini I: le pouvoir de l'interaction. J. ACM 39, 4 (octobre 1992), 800-828. DOI = http://doi.acm.org/10.1145/146585.146599

ou le document correspondant:

Dwork, C. et Stockmeyer, L. 1992. Vérificateurs d'état fini II: connaissance zéro. J. ACM 39, 4 (octobre 1992), 829-858. DOI = http://doi.acm.org/10.1145/146585.146601

MS Dousti
la source
J'ai déjà parcouru ces articles et d'autres de Condon, Lipton et al., Mais il n'y a rien là-bas concernant les propriétés de fermeture de ces classes.
Cem Say
1
@Cem: Pouvez-vous clarifier la définition de "fermeture"? En particulier, dans quel type d'opération demandez-vous la fermeture?
MS Dousti