[comp_complex] Hints for Assignment 6

  • From: "Christian Scheideler" <scheideler@xxxxxxxxxx>
  • To: <comp_complex@xxxxxxxxxxxxx>
  • Date: Fri, 26 Mar 2004 16:48:57 -0500


Since I will not be around next week (someone else will give the
lectures for me), here are some hints for Assignment 6:

Problem 17: The proof pi can potentially be of infinite length. The
problem is that the verifier can only access bits in pi that have an
address of at most 2^{poly(|x|)} (x: input) because the polynomial time
requirement only allows the verifier to use poly(|x|) many bits for
specifying an address in pi. So it is important to find a way of glueing
the individual proofs pi_x for all possible inputs x together so that
for any particular x its proof part in pi has addresses that can be
specified with poly(|x|) bits.

Problem 18: You can assume here that the verifier is non-adaptive.

Problem 19: Just give an explanation of how to do the extension (but try
to be formal in your arguments). You do not have to repeat the entire
proof of Theorem 8.3.

I hope that helps.

Christian Scheideler

Other related posts: