next up previous
Next: About this document Up: No Title Previous: No Title

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

  1. Osoita, että jos tex2html_wrap_inline709 on polynomisessa ajassa laskettava funktio, niin jokaisella merkkijonolla tex2html_wrap_inline711 kuuluu alkukuvajoukko tex2html_wrap_inline713 luokkaan P. Yleistä tulos koskemaan kaikkia alkukuvajoukkoja tex2html_wrap_inline715 , missä tex2html_wrap_inline717 .
  2. Osoita, että luokat P ja PSPACE ovat suljettuja yhdisteiden, leikkausten ja komplementtien suhteen.
  3. 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?
  4. Koska luokan NP ei tiedetä olevan suljettu komplementoinnin suhteen, on mielenkiintoista tarkastella sen duaaliluokkaa

    displaymath705

    Todista seuraavat luokan co-NP ominaisuudet:

    1. tex2html_wrap_inline721 ;
    2. tex2html_wrap_inline723 ;
    3. jos tex2html_wrap_inline725 , niin tex2html_wrap_inline727 ja tex2html_wrap_inline729 ;
    4. kieli A on co-NP-täydellinen, jos ja vain jos kieli tex2html_wrap_inline733 on NP-täydellinen.
  5. Funktio tex2html_wrap_inline735 on tilakonstruoituva, jos jollakin deterministisellä moninauhaisella Turingin koneella M on voimassa: tex2html_wrap_inline739 kaikilla syötejonoilla x. Todista seuraavat väitteet:
    1. Funktiot s(n) = k (vakio), s(n) = n ja tex2html_wrap_inline747 ovat tilakonstruoituvia.
    2. Jos tex2html_wrap_inline749 ja tex2html_wrap_inline751 ovat tilakonstruoituvia, niin myös tex2html_wrap_inline753 , tex2html_wrap_inline755 ja tex2html_wrap_inline757 ovat tilakonstruoituvia.
    3. Jokaisella rekursiivisella funktiolla r(n) on olemassa tilakonstruoituva tex2html_wrap_inline761 .
  6. Todista, että jokaisella tilakonstruoituvalla tex2html_wrap_inline763 on voimassa sisältyvyys

    displaymath706

    (Vihje: Muodosta verkko, jonka solmut ovat simuloitavan epädeterministisen koneen tilannekuvauksia.)



Pekka Orponen
Thu Feb 3 19:13:02 EET 2000