I'm currently trying to gain an understanding of verifiable computation and the strengths and weaknesses of past approaches.
In particular, I've been watching the following YouTube video which talks about interactive proofs as a way of verifying knowledge of a computation. On the slide appearing during time 11:55, it mentions that the prover requires exponential time in the space of the computation. Could anyone explain how this is the case?
I'm also confused as to the statement which says that every deterministic computation has an interactive proof.
I've tried reading the papers below but can't seem to find a clear explanation of these results. Any help would be much appreciated!
References:
Lund, Carsten, et al. "Algebraic methods for interactive proof systems." Journal of the ACM (JACM) 39.4 (1992): 859-868.
Shamir, Adi. "Ip= pspace." Journal of the ACM (JACM) 39.4 (1992): 869-877.