[comp_complex] Re: Hints for Assignment 6

  • 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
>
>


Other related posts: