Tietojenkäsittelyteoria, kevät 2000
Harjoitus 10, to 30.3. klo 10-12 sali MaD381

1. Esitä Lucasin testiin (luentojen s. 8.20) perustuva ``NP-todistuspuu'', joka vahvistaa että 11 on alkuluku.
2. [Siirtynyt harjoituksista 9.] Osoita, että jos , niin . (Vihje: SATin totuusarvoasetuksen oikeellisuuden voi tarkastaa.)
3. Sanotaan, että kieli A kuuluu luokkaan BPNP (kirjallisuudessa käytetään myös merkintää AM), jos on olemassa kieli ja polynomi p(n), joilla:

   (i)

   jos , niin ;

   (ii)

   jos , niin .

   Osoita, että . Ohje: Totea ensin, luentojen Lauseen 8.10 tapaan, että virhetodennäköisyys 1/3 voidaan pienentää luokkaan , millä tahansa polynomilla q(n). Seuraa sitten luentojen Lauseen 8.13 todistusta, käyttäen seuraavaa kielen A karakterisointia ``ison'' kielen B avulla:

   

4. [Jatkoa edelliseen.] Osoita, että jos , niin . Päättele tästä, että jos verkkoisomorfiaongelma (kieli GISO) on NP-täydellinen, niin .
5. Jäljittele kielen QBF vuorovaikutteista todistusprotokollaa, jolla
   1. todistaja P vakuuttaa varmentajan V väitteen totuudesta;
   2. todistaja P yrittää vakuuttaa varmentajan V väitteen totuudesta, mutta epäonnistuu.