propriedades de fechamento de IP (2pfa) e AM (2pfa)

9

IP (2pfa) e AM (2pfa) são as classes de idiomas reconhecidas com erro limitado por versões de moedas públicas e privadas, respectivamente, de sistemas de provas interativas com verificadores que são autômatos finitos probabilísticos com um cabeçote de entrada bidirecional.

Existem propriedades de fechamento dessas classes conhecidas?

Cem Say
fonte

Respostas:

2

Você pode dar uma olhada no seguinte documento:

Dwork, C. e Stockmeyer, L. 1992. Verificadores de estado finito I: o poder da interação. J. ACM 39, 4 (outubro de 1992), 800-828. DOI = http://doi.acm.org/10.1145/146585.146599

ou o trabalho relacionado:

Dwork, C. e Stockmeyer, L. 1992. Verificadores de estado finito II: zero conhecimento. J. ACM 39, 4 (outubro de 1992), 829-858. DOI = http://doi.acm.org/10.1145/146585.146601

MS Dousti
fonte
Eu já examinei esses papéis e outros de Condon, Lipton et al., Mas não há nada sobre as propriedades de fechamento dessas classes.
Cem Say
11
@ Cec: Você pode esclarecer sobre a definição de "encerramento"? Em particular, em que tipo de operação você busca o fechamento?
MS Dousti 23/09/10