Algoritmiteorian jatkokurssi, kevät 1999
Harjoitus 5, 3.5. klo 10-12 sali MaD380

1. Osoita, että mitään -palautusten suhteen EXPSPACE-kovaa kieltä ei voida tunnistaa polynomista kokoa olevilla kombinaatiopiireillä. Onko tulos voimassa myös -palautuksille?
2. Osoita, että

   

   (Vrt. luentojen Lause 7.11.)

3. Tarkastellaan vaativuusluokkaa ZPP = R co-R. Osoita, että jos kieli A kuuluu luokkaan ZPP, niin se voidaan tunnistaa satunnaisalgoritmilla, joka ei koskaan anna väärää vastausta, mutta jonka suoritusaika on polynominen ainoastaan odotusarvoisesti (so. huonolla onnella algoritmin suoritus voi kestää hyvinkin kauan). (Vihje: Simuloi kielen A ja tunnistavia R-koneita rinnakkain.)
4. Luentomonisteen Lemma 8.8 sisältää seuraavan yksinkertaisen, mutta tärkeän ``todennäköisyysvahvistustuloksen'': Jos , niin millä tahansa polynomilla q on olemassa polynomisessa ajassa toimiva probabilistinen Turingin kone M, jolla L(M)=A ja kaikilla x. Tuloksen todistuksessa monisteen s. 80 on valitettavasti virhe. Korjaa todistus. (Vihje: Sovella ns. Chernoffin rajoja. Tehtävä on oleellisesti sama kuin kevään Algoritmien teoria -kurssin harjoitusten 7 tehtävä 3, jonka malliratkaisukin löytynee edelleen kurssin kurssimapista.)