patternMinor
Why there is no constraint on "Prover" in definition of $IP$?
Viewed 0 times
definitionwhyconstraintproverthere
Problem
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 ?
Also the book says the "Prover" might compute some undecidable function. How is that possible ? Am I missing something trivial ?
Solution
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.
things from TFUP to [CH given a polynomial-length string] might give intermediate classes.
Context
StackExchange Computer Science Q#55170, answer score: 4
Revisions (0)
No revisions yet.