9
$\begingroup$

IP(2pfa) and AM(2pfa) are the classes of languages recognized with bounded error by private and public coin versions, respectively, of interactive proof systems with verifiers that are probabilistic finite automata with a two-way input head.

Are any closure properties of these classes known?

$\endgroup$
2
$\begingroup$

You can take a look at the following paper:

Dwork, C. and Stockmeyer, L. 1992. Finite state verifiers I: the power of interaction. J. ACM 39, 4 (Oct. 1992), 800-828. DOI= http://doi.acm.org/10.1145/146585.146599

or the related paper:

Dwork, C. and Stockmeyer, L. 1992. Finite state verifiers II: zero knowledge. J. ACM 39, 4 (Oct. 1992), 829-858. DOI= http://doi.acm.org/10.1145/146585.146601

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I've already gone through those papers and others by Condon, Lipton et al., but there's nothing there about the closure properties of these classes. $\endgroup$ – Cem Say Sep 23 '10 at 10:25
  • 1
    $\begingroup$ @Cem: Can you clarify on the definition of "closure"? In particular, under what kind of operation do you seek closure? $\endgroup$ – M.S. Dousti Sep 23 '10 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.