# The relation between NP and IP(2pfa)

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.
• Is $IP(2pfa)\subseteq NP$? – Marcos Villagra Oct 16 '12 at 6:51
• 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)]. – Abuzer Yakaryilmaz Oct 16 '12 at 9:03