Next: About this document
Up: No Title
Previous: No Title
-
Esitä Lucasin testiin (luentojen s. 8.20) perustuva
``NP-todistuspuu'', joka vahvistaa että 11 on alkuluku.
- [Siirtynyt harjoituksista 9.]
Osoita, että jos , niin .
(Vihje: SATin totuusarvoasetuksen oikeellisuuden
voi tarkastaa.)
-
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:
- [Jatkoa edelliseen.]
Osoita, että jos , niin .
Päättele tästä, että jos verkkoisomorfiaongelma (kieli GISO) on
NP-täydellinen, niin .
-
Jäljittele kielen QBF vuorovaikutteista todistusprotokollaa, jolla
- todistaja P vakuuttaa varmentajan V väitteen
totuudesta;
- todistaja P yrittää vakuuttaa varmentajan V väitteen
totuudesta, mutta epäonnistuu.
Pekka Orponen
Thu Mar 23 20:06:39 EET 2000