4
$\begingroup$

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 ?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If there are no constraints on the "prover" then can't we just take prover to be the oracle for the problem. Like this all languages belong to IP. What is the constraint I am missing ? $\endgroup$ – sashas Mar 31 '16 at 9:53
  • $\begingroup$ What would the verifier do? ​ (You're probably missing soundness.) ​ ​ ​ ​ $\endgroup$ – user12859 Mar 31 '16 at 10:38
  • $\begingroup$ So do you mean that the verifier must be able to verify in polynomial time, whatever the prover messages/aids it ? $\endgroup$ – sashas Mar 31 '16 at 12:40
  • $\begingroup$ No, although it must use the communication to assure itself that the instance is not a NO instance. ​ ​ $\endgroup$ – user12859 Mar 31 '16 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.