<p>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 (<a href="http://dl.acm.org/citation.cfm?doid=146585.146599" rel="nofollow">Finite state verifiers I: the power of interaction</a> by Dwork and Stockmeyer).</p>

<p>Does anybody know any progress on this issue?</p>

<p>I know the following results:</p>

<ul>
<li>$ \mathsf{IP(2pfa)} $ contains some NP-complete languages, where the verifier runs in poly-time.</li>
<li>$ \mathsf{P} \subseteq \mathsf{IP(2pfa)} $, where the verifier runs in exp-time.</li>
<li>$ \mathsf{DTIME(2^{O(n)})} \subseteq \mathsf{IP(2pfa)} $, where the verifier runs in double-exp-time.</li>
</ul>

CC BY-SA 3.0
2012-10-16T06:51:26.773Z
Is $IP(2pfa)\subseteq NP$?
Marcos Villagra
CC BY-SA 3.0
2012-10-16T09:03:48.890Z
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 (http://doi.ieeecomputersociety.org/10.1109/SFCS.1989.63519)].
Abuzer Yakaryilmaz
<cc.complexity-theory><reference-request><cr.crypto-security><np><interactive-proofs>
The relation between NP and IP(2pfa)
Abuzer Yakaryilmaz
# The relation between NP and IP(2pfa)

(Asked by: username_0 on 2012-09-20)

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](http://dl.acm.org/citation.cfm?doid=146585.146599) 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.

**Tags:** cc.complexity-theory, reference-request, cr.crypto-security, np, interactive-proofs

> **Comments:**
> **username_1**: Is $IP(2pfa)\subseteq NP$?  
> **username_0**: 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 (http://doi.ieeecomputersociety.org/10.1109/SFCS.1989.63519)].  

---

## 0 answers

