<p>I try to understand the advantages of using a probabilistic polynomial-time verifier instead of an determininistic one. I use as literature "Arora, Barak: Computational Complexity", in which the class $dIP$ is defined as languages where a deterministic polynomial-time proof system exists. I also undestand that $dIP = NP$. Now, the class $IP$ is defined as class where the languages have an interactive polynomial-time proof system, where the verifier works probabilistic. Shamir proved, that $IP = PSPACE$, this means, all PSPACE problems can be interactive proved in probabilistic polynomial time </p>

<p>Now, I am still asking myself if there are any advantages of class $IP$ without looking at $PSPACE$ problems? By knowing that $dIP = NP \subseteq IP = PSPACE$, I can use a deterministic polynomial-time interactive proof system and also a probabilistic polynomial-time proof system for a language in $NP$. The deterministic version would take one-round, because the verifier can ask the prover for the whole $NP$ witness. But, $NP$ witness are not "short", so, would be a probabilistic system with multiple rounds but shorter size (thus not the complete $NP$ witness) better?</p>

CC BY-SA 3.0
2017-05-29T18:24:52.327Z
You may also check space-bounded IPS that you might also find interesting: http://www.cs.ubc.ca/~condon/papers/ips-survey.pdf  You can also check this blog entry: https://rjlipton.wordpress.com/2009/03/19/the-unbounded-power-of-randomness/
Abuzer Yakaryilmaz
CC BY-SA 3.0
2017-05-29T19:22:34.633Z
How do you define "better"? There is some work on efficient interactive proofs, where efficiency is measured in terms of the running time of the prover or verifier and also in terms of communication. Is that what you are looking for?
Sasho Nikolov
CC BY-SA 3.0
2017-05-29T21:17:51.783Z
The question in the title is quite different from the actual question you pose. Wouldn't $MIP=NEXP$ be enough justification?
domotorp
<interactive-proofs>
Is $IP$ only interesting because of the equality to $PSPACE$?
Burak
# Is $IP$ only interesting because of the equality to $PSPACE$?

(Asked by: username_0 on 2017-05-29)

I try to understand the advantages of using a probabilistic polynomial-time verifier instead of an determininistic one. I use as literature "Arora, Barak: Computational Complexity", in which the class $dIP$ is defined as languages where a deterministic polynomial-time proof system exists. I also undestand that $dIP = NP$. Now, the class $IP$ is defined as class where the languages have an interactive polynomial-time proof system, where the verifier works probabilistic. Shamir proved, that $IP = PSPACE$, this means, all PSPACE problems can be interactive proved in probabilistic polynomial time

Now, I am still asking myself if there are any advantages of class $IP$ without looking at $PSPACE$ problems? By knowing that $dIP = NP \subseteq IP = PSPACE$, I can use a deterministic polynomial-time interactive proof system and also a probabilistic polynomial-time proof system for a language in $NP$. The deterministic version would take one-round, because the verifier can ask the prover for the whole $NP$ witness. But, $NP$ witness are not "short", so, would be a probabilistic system with multiple rounds but shorter size (thus not the complete $NP$ witness) better?

**Tags:** interactive-proofs

> **Comments:**
> **username_1**: You may also check space-bounded IPS that you might also find interesting: http://www.cs.ubc.ca/~condon/papers/ips-survey.pdf  You can also check this blog entry: https://rjlipton.wordpress.com/2009/03/19/the-unbounded-power-of-randomness/  
> **username_2**: How do you define "better"? There is some work on efficient interactive proofs, where efficiency is measured in terms of the running time of the prover or verifier and also in terms of communication. Is that what you are looking for?  
> **username_3**: The question in the title is quite different from the actual question you pose. Wouldn't $MIP=NEXP$ be enough justification?  

---

## 0 answers

