Cheap and Secure Web Hosting Provider : See Now

[Answers] Why there is no constraint on "Prover" in definition of $IP$?

, , No Comments
Problem Detail: 

According to the definition of $IP$ given in Sanjeev Arora and Barak there is no constraint on the running time of the "Prover" ( when "verifier" sends a message to the "Prover" and expects a message in return from it ). Why is it so ? Also the book says the "Prover" might compute some undecidable function. How is that possible ? Am I missing something trivial ?

Asked By : sashas

Answered By : Ricky Demer

There's nothing canonical for what constraint one might put on it. ​ Requiring complete efficiency would give BPP, since the algorithm can just simulate the whole interaction. ​ Requiring efficient-given-a-polynomial-length-string would give MA, since the prover could just send its string to the verifier. ​ It turns out that PSPACE is always enough, so letting the prover be at least that powerful yields the same class as not constraining the prover. ​ I suppose
things from TFUP to [CH given a polynomial-length string] might give intermediate classes.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback