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

Hi, 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

**Follow-Ups**:**[comp_complex] Re: Hints for Assignment 6***From:*David Friedman

- » [comp_complex] Hints for Assignment 6
- » [comp_complex] Re: Hints for Assignment 6