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?

  • 1
    $\begingroup$ You may also check space-bounded IPS that you might also find interesting: cs.ubc.ca/~condon/papers/ips-survey.pdf You can also check this blog entry: rjlipton.wordpress.com/2009/03/19/… $\endgroup$ May 29, 2017 at 18:24
  • 3
    $\begingroup$ 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? $\endgroup$ May 29, 2017 at 19:22
  • 7
    $\begingroup$ The question in the title is quite different from the actual question you pose. Wouldn't $MIP=NEXP$ be enough justification? $\endgroup$
    – domotorp
    May 29, 2017 at 21:17


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.