<p>You can find many characterizations (particularly on space-bounded verifiers) in Condon's famous survey: <a href="http://www.cs.ubc.ca/~condon/papers/ips-survey.pdf">The complexity of space bounded interactive proof systems</a>.</p>

<p>Here is a list of some of them:</p>

<ul>
<li><p>$ \mathsf{RE} = \mathsf{weak\mbox{-}IP(2pfa)} $, where 2pfa (the verifier) is a two-way probabilistic finite automaton.</p></li>
<li><p>$ \mathsf{R} = \mathsf{2IP(pfa)} $, where pfa (the verifier) is a one-way probabilistic finite automaton interacting with two provers.</p></li>
<li><p>$ \mathsf{NEXP} = \mathsf{2IP(pfa,poly\mbox{-}time)} $.</p></li>
<li><p>$ \mathsf{PSPACE} = \mathsf{IP(log\mbox{-}space,poly\mbox{-}time)} $.</p></li>
<li><p>$ \mathsf{NP} = \mathsf{oneway\mbox{-}IP(log\mbox{-}space,poly\mbox{-}time)} = \mathsf{oneway\mbox{-}IP(log\mbox{-}space,log\mbox{-}random\mbox{-}bits)} $.</p></li>
<li><p>$ \mathsf{P} = \mathsf{AM(log\mbox{-}space)} $, $ \mathsf{EXP} = \mathsf{AM(poly\mbox{-}space)} $, and etc.</p></li>
</ul>

<hr>

<p>Some recent (mostly quantum) results:</p>

<ul>
<li><p>$ \mathsf{RE} = \mathsf{weak\mbox{-}AM(2qcfa)} $ by <a href="http://arxiv.org/abs/1205.5395">Yakaryilmaz</a>, where 2qcfa (the verifier) is a two-way finite automaton having a constant-size quantum register.</p></li>
<li><p>$ \mathsf{R} = \mathsf{IP(2pca)} = \mathsf{AM(2qca)} $ by <a href="http://eccc.hpi-web.de/report/2012/091/">Yakaryilmaz</a>, where 2pca (the former verifier) is a two-way probabilistic finite automaton with one counter and 2qca (the latter verifier) is a two-way quantum finite automaton with one counter.</p></li>
<li><p><a href="http://dl.acm.org/citation.cfm?doid=2090236.2090259">Ito, Kobayashi, and Watrous</a> gave a new characterization of $ \mathsf{EXP} $ based on quantum interactive proof systems with a double-exponentially small gap in acceptance probability between the completeness and soundness cases.</p></li>
<li><p>$ \mathsf{PSPACE} = \mathsf{QIP(poly\mbox{-}time)} $ by <a href="http://dl.acm.org/citation.cfm?doid=2049697.2049704">Jain, Ji, Upadhyay, and Watrous</a>, where QIP is the quantum generalization of IP systems.</p></li>
<li><p>$ \mathsf{NP} $ is the class of languages for which membership has a logarithmic-size quantum proof with perfect completeness and soundness, which is polynomially close to 1 in a context where the verifier is provided a proof with two unentangled parts (<a href="http://www.springerlink.com/content/m53u141735462m33/">Blier and Tapp</a>).</p></li>
<li><p>$ \mathsf{NL} = \mathsf{weak\mbox{-}oneway\mbox{-}IP(2pfa,constant\mbox{-}random\mbox{-}bits)} $ by <a href="http://dx.doi.org/10.1007/978-3-642-30870-3_65">Say and Yakaryilmaz</a>.</p></li>
</ul>

CC BY-SA 3.0
2012-08-22T23:47:37.510Z
Thanks! This is exactly what I wanted. I was at a loss of how to improve my question, which was too vague for experts, and am glad you understood my intent.
Vijay D
CC BY-SA 3.0
2012-08-23T13:09:25.147Z
Well, then, why don't you mark it as the best answer?
Cem Say
CC BY-SA 3.0
2012-08-24T08:17:49.997Z
Because who knows what tomorrow will bring? I would like to a week or 10 days after posting to decide.
Vijay D
CC BY-SA 3.0
2012-08-22T20:56:39.807Z
2012-08-23T08:23:21.753Z
2012-08-23T08:23:21.753Z
Abuzer Yakaryilmaz
<p>NP is ofter characterized as a proof system in which the prover sends a polynomial-length proof to a deterministic polynomial-time verifier, and after which there is no interaction. The class of recursively enumerable languages can be characterized similarly by replacing "polynomial" with "finite".</p>

<p>Also, since the class of recursive languages R is the intersection of RE and coRE, you can characterize R as a proof system in which an all-mighty prover can convince a finite time verifier both in the validity of correct claims and in the invalidity of false claims.</p>

<p>The class EXP has a characterization in terms of a proof system with "competing provers" - i.e., a proof system in which there is a prover that tries to convince the verifier that the claim is true and a refuter that tries to convince the verifier that the claim is false. See the paper "Making games short" of Feige and Kilian for more details.  </p>

CC BY-SA 3.0
2012-08-20T04:25:30.190Z
2012-08-21T21:00:57.600Z
2012-08-21T21:00:57.600Z
Or Meir
<p>My first question is whether an interactive proof system characterisation is known for all the classic complexity classes. I would call P, NP, PSPACE, EXP, NEXP,EXPSPACE, recursive and recursively enumerable functions classic (among others). Specifically,is an interactive proof system characterisation known for recursive and recursively enumerable functions?</p>

<p>I only know that IP = PSPACE and that MIP = NEXPTIME. By `know'  means I understand the definitions of objects on both sides of the equality and possibly understand the equality.</p>

<p>My second question is whether there is a graphical summary of different types of interactive proof systems and the complexity classes they characterise.</p>

<p>Specifically, I would like a reference to a figure similar to Immerman's picture of <a href="http://people.cs.umass.edu/~immerman/descriptiveWorld.jpg">description complexity characterisations</a>.</p>

CC BY-SA 3.0
2012-08-19T12:33:51.890Z
What do you already know?
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-19T17:03:27.527Z
There is more than 1 variable parameter in an interactive proof system: What's the power of the verifier, what's the power of the prover, what kind (and amount) of communication are they allowed, do they have pre-shared randomness, does the verifier have to read the entire message from the prover or does he have random access to the message, etc.
Robin Kothari
CC BY-SA 3.0
2012-08-19T22:02:55.967Z
@TsuyoshiIto, I know very little and mentioned it above.
Vijay D
CC BY-SA 3.0
2012-08-19T22:08:36.630Z
@RobinKothari: different parameters is fine and to be expected. Do you mention it because the same class has different characterisations?
Vijay D
CC BY-SA 3.0
2012-08-19T22:10:25.393Z
Thank you for the edit.  Before the edit, I was not sure where to start—you may or may not know IP=PSPACE, you may or may not know MIP=NEXP.  Not that I can write up an answer soon, because you are asking quite a lot, but the question is better than before because it is a little more concrete.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-19T22:16:09.520Z
After a little more thinking, I do not think that I can answer your question adequately because interactive proof system is a broad topic in computational complexity theory.  You may want to check Chapter 9 of _Computational Complexity: A Conceptual Perspective_ by Goldreich or Chapters 8 and 11 of _Computational Complexity: A Modern Approach_ by Arora and Barak.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-19T22:21:17.280Z
@VijayD: Yes, that's part of the issue. In descriptive complexity characterizations, there's one variable (the logic), so as you go higher up from FO to SO, you go from AC0 to PH, etc. In interactive proof systems, there are so many variables that it's not clear that a nice landscape can be drawn.
Robin Kothari
CC BY-SA 3.0
2012-08-20T08:01:54.043Z
I am not sure this question is well-specified enough. There is a trivial answer: every class can be "characterized" as an "interactive proof" where the prover basically does not do much and the verifier is powerful enough. The interesting thing about the IP=PSPACE and MIP=NEXP (and PCP[O(\log n), O(1)]=NP) results is that the verifier is surprisingly weak.
Sasho Nikolov
CC BY-SA 3.0
2012-08-20T17:01:44.397Z
@RobinKothari: I'm not sure it's an issue. In logic, there is FO-SO, quantifier alternation depth, the class of structures considered, which are independent dimensions. Immerman labels a standard inclusion picture of complexity classes with logics. I would like to know the same for interactive proof systems.
Vijay D
<cc.complexity-theory><big-picture><interactive-proofs>
Landscape of interactive proof systems
Vijay D
# Landscape of interactive proof systems

(Asked by: username_0 on 2012-08-19)

My first question is whether an interactive proof system characterisation is known for all the classic complexity classes. I would call P, NP, PSPACE, EXP, NEXP,EXPSPACE, recursive and recursively enumerable functions classic (among others). Specifically,is an interactive proof system characterisation known for recursive and recursively enumerable functions?

I only know that IP = PSPACE and that MIP = NEXPTIME. By `know' means I understand the definitions of objects on both sides of the equality and possibly understand the equality.

My second question is whether there is a graphical summary of different types of interactive proof systems and the complexity classes they characterise.

Specifically, I would like a reference to a figure similar to Immerman's picture of [description complexity characterisations](http://people.cs.umass.edu/~immerman/descriptiveWorld.jpg).

**Tags:** cc.complexity-theory, big-picture, interactive-proofs
> **Comments:**
> **username_1**: What do you already know?  
> **username_2**: There is more than 1 variable parameter in an interactive proof system: What's the power of the verifier, what's the power of the prover, what kind (and amount) of communication are they allowed, do they have pre-shared randomness, does the verifier have to read the entire message from the prover or does he have random access to the message, etc.  
> **username_0**: @TsuyoshiIto, I know very little and mentioned it above.  
> **username_0**: @RobinKothari: different parameters is fine and to be expected. Do you mention it because the same class has different characterisations?  
> **username_1**: Thank you for the edit.  Before the edit, I was not sure where to start—you may or may not know IP=PSPACE, you may or may not know MIP=NEXP.  Not that I can write up an answer soon, because you are asking quite a lot, but the question is better than before because it is a little more concrete.  
> **username_1**: After a little more thinking, I do not think that I can answer your question adequately because interactive proof system is a broad topic in computational complexity theory.  You may want to check Chapter 9 of _Computational Complexity: A Conceptual Perspective_ by Goldreich or Chapters 8 and 11 of _Computational Complexity: A Modern Approach_ by Arora and Barak.  
> **username_2**: @VijayD: Yes, that's part of the issue. In descriptive complexity characterizations, there's one variable (the logic), so as you go higher up from FO to SO, you go from AC0 to PH, etc. In interactive proof systems, there are so many variables that it's not clear that a nice landscape can be drawn.  
> **username_3**: I am not sure this question is well-specified enough. There is a trivial answer: every class can be "characterized" as an "interactive proof" where the prover basically does not do much and the verifier is powerful enough. The interesting thing about the IP=PSPACE and MIP=NEXP (and PCP[O(\log n), O(1)]=NP) results is that the verifier is surprisingly weak.  
> **username_0**: @RobinKothari: I'm not sure it's an issue. In logic, there is FO-SO, quantifier alternation depth, the class of structures considered, which are independent dimensions. Immerman labels a standard inclusion picture of complexity classes with logics. I would like to know the same for interactive proof systems.  

---

## 2 answers

### Answer by username_4 on 2012-08-22. Score: 12 | Accepted answer

You can find many characterizations (particularly on space-bounded verifiers) in Condon's famous survey: [The complexity of space bounded interactive proof systems](http://www.cs.ubc.ca/~condon/papers/ips-survey.pdf).

Here is a list of some of them:

* $ \mathsf{RE} = \mathsf{weak\mbox{-}IP(2pfa)} $, where 2pfa (the verifier) is a two-way probabilistic finite automaton.
* $ \mathsf{R} = \mathsf{2IP(pfa)} $, where pfa (the verifier) is a one-way probabilistic finite automaton interacting with two provers.
* $ \mathsf{NEXP} = \mathsf{2IP(pfa,poly\mbox{-}time)} $.
* $ \mathsf{PSPACE} = \mathsf{IP(log\mbox{-}space,poly\mbox{-}time)} $.
* $ \mathsf{NP} = \mathsf{oneway\mbox{-}IP(log\mbox{-}space,poly\mbox{-}time)} = \mathsf{oneway\mbox{-}IP(log\mbox{-}space,log\mbox{-}random\mbox{-}bits)} $.
* $ \mathsf{P} = \mathsf{AM(log\mbox{-}space)} $, $ \mathsf{EXP} = \mathsf{AM(poly\mbox{-}space)} $, and etc.

---

Some recent (mostly quantum) results:

* $ \mathsf{RE} = \mathsf{weak\mbox{-}AM(2qcfa)} $ by [Yakaryilmaz](http://arxiv.org/abs/1205.5395), where 2qcfa (the verifier) is a two-way finite automaton having a constant-size quantum register.
* $ \mathsf{R} = \mathsf{IP(2pca)} = \mathsf{AM(2qca)} $ by [Yakaryilmaz](http://eccc.hpi-web.de/report/2012/091/), where 2pca (the former verifier) is a two-way probabilistic finite automaton with one counter and 2qca (the latter verifier) is a two-way quantum finite automaton with one counter.
* [Ito, Kobayashi, and Watrous](http://dl.acm.org/citation.cfm?doid=2090236.2090259) gave a new characterization of $ \mathsf{EXP} $ based on quantum interactive proof systems with a double-exponentially small gap in acceptance probability between the completeness and soundness cases.
* $ \mathsf{PSPACE} = \mathsf{QIP(poly\mbox{-}time)} $ by [Jain, Ji, Upadhyay, and Watrous](http://dl.acm.org/citation.cfm?doid=2049697.2049704), where QIP is the quantum generalization of IP systems.
* $ \mathsf{NP} $ is the class of languages for which membership has a logarithmic-size quantum proof with perfect completeness and soundness, which is polynomially close to 1 in a context where the verifier is provided a proof with two unentangled parts ([Blier and Tapp](http://www.springerlink.com/content/m53u141735462m33/)).
* $ \mathsf{NL} = \mathsf{weak\mbox{-}oneway\mbox{-}IP(2pfa,constant\mbox{-}random\mbox{-}bits)} $ by [Say and Yakaryilmaz](http://dx.doi.org/10.1007/978-3-642-30870-3_65).

> **Comments:**
> **username_0**: Thanks! This is exactly what I wanted. I was at a loss of how to improve my question, which was too vague for experts, and am glad you understood my intent.  
> **username_5**: Well, then, why don't you mark it as the best answer?  
> **username_0**: Because who knows what tomorrow will bring? I would like to a week or 10 days after posting to decide.  

---

### Answer by username_6 on 2012-08-20. Score: 16

NP is ofter characterized as a proof system in which the prover sends a polynomial-length proof to a deterministic polynomial-time verifier, and after which there is no interaction. The class of recursively enumerable languages can be characterized similarly by replacing "polynomial" with "finite".

Also, since the class of recursive languages R is the intersection of RE and coRE, you can characterize R as a proof system in which an all-mighty prover can convince a finite time verifier both in the validity of correct claims and in the invalidity of false claims.

The class EXP has a characterization in terms of a proof system with "competing provers" - i.e., a proof system in which there is a prover that tries to convince the verifier that the claim is true and a refuter that tries to convince the verifier that the claim is false. See the paper "Making games short" of Feige and Kilian for more details.


---

