As far as I know, it is not known whether $ \mathsf{NP} \subseteq \mathsf{IP(2pfa)} $, where $ \mathsf{IP(2pfa)} $ is the class of languages having interactive proof systems with some two-way probabilistic finite automata verifiers (Finite state verifiers I: the power of interaction by Dwork and Stockmeyer).

Does anybody know any progress on this issue?

I know the following results:

  • $ \mathsf{IP(2pfa)} $ contains some NP-complete languages, where the verifier runs in poly-time.
  • $ \mathsf{P} \subseteq \mathsf{IP(2pfa)} $, where the verifier runs in exp-time.
  • $ \mathsf{DTIME(2^{O(n)})} \subseteq \mathsf{IP(2pfa)} $, where the verifier runs in double-exp-time.
  • 1
    $\begingroup$ Is $IP(2pfa)\subseteq NP$? $\endgroup$ – Marcos Villagra Oct 16 '12 at 6:51
  • $\begingroup$ The best known upper for $ \mathsf{IP(2pfa)} $ is $ \mathsf{ATIME(2^{2^{O(n)}})} $ [Anne Condon, Richard J. Lipton: On the Complexity of Space Bounded Interactive Proofs (Extended Abstract) FOCS 1989: 462-467 (doi.ieeecomputersociety.org/10.1109/SFCS.1989.63519)]. $\endgroup$ – Abuzer Yakaryilmaz Oct 16 '12 at 9:03

Your Answer

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

Browse other questions tagged or ask your own question.