*From*: David Friedman <dkf@xxxxxxxxxx>*To*: <comp_complex@xxxxxxxxxxxxx>*Date*: Wed, 31 Mar 2004 21:31:13 -0500 (EST)

On Fri, 26 Mar 2004, Christian Scheideler wrote: > 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. This is the correct statement: that the size of each proof string (Pi_i) is exponentially long, not polynomially long. David > > 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 > >

**References**:**[comp_complex] Hints for Assignment 6***From:*Christian Scheideler

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