Algoritmiteorian jatkokurssi, kevät 1999
Harjoitus 1, 29.3. klo 10-12 sali MaD380

1. Palautetaan mieliin Automaatit ja kieliopit -kurssilta, että formaali kieli A on säännöllinen, jos se voidaan tunnistaa äärellisellä automaatilla. Mitä voit sanoa säännöllisten kielten tunnistamisen vaativuudesta Turingin kone -mallissa (so. millaisilla aika- ja tilarajoilla t(n) ja s(n) saadaan kaikki säännölliset kielet mukaan luokkiin ja )?
2. Olkoon jokin Turingin koneiden efektiivinen luettelointi. (Vrt. Automaatit ja kieliopit -kurssi.) Osoita, että jos t(n) on rekursiivinen funktio, niin kieli

   

   on rekursiivinen, mutta ei kuulu luokkaan .

3. Osoita, että jos on polynomisessa ajassa laskettava funktio, niin jokaisella merkkijonolla kuuluu alkukuvajoukko luokkaan P. Yleistä tulos koskemaan kaikkia alkukuvajoukkoja , missä .
4. Osoita, että luokka P on suljettu yhdisteiden, leikkausten ja komplementtien suhteen.
5. Osoita, että luokka NP on suljettu yhdisteiden ja leikkausten suhteen. Luokan ei tiedetä olevan suljettu komplementoinnin suhteen: mihin vaikeuteen törmätään yritettäessä todistaa tätä ominaisuutta?
6. Koska luokan NP ei tiedetä olevan suljettu komplementoinnin suhteen, on mielenkiintoista tarkastella sen duaaliluokkaa

   

   Todista seuraavat luokan co-NP ominaisuudet:

   1. ;
   2. ;
   3. jos , niin ja .
   (Vihje: Komplementointi.)