Osoita, että jos on polynomisessa
ajassa laskettava funktio, niin jokaisella merkkijonolla
kuuluu alkukuvajoukko luokkaan P. Yleistä tulos koskemaan
kaikkia alkukuvajoukkoja , missä .
Osoita, että luokat P ja PSPACE ovat suljettuja yhdisteiden,
leikkausten ja komplementtien suhteen.
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?
Koska luokan NP ei tiedetä olevan suljettu komplementoinnin suhteen,
on mielenkiintoista tarkastella sen duaaliluokkaa
Todista seuraavat luokan co-NP ominaisuudet:
;
;
jos , niin ja ;
kieli A on co-NP-täydellinen, jos ja vain jos kieli
on NP-täydellinen.
Funktio on
tilakonstruoituva, jos jollakin deterministisellä moninauhaisella
Turingin koneella
M on voimassa: kaikilla syötejonoilla x.
Todista seuraavat väitteet:
Funktiot s(n) = k (vakio), s(n) = n ja
ovat tilakonstruoituvia.
Jos ja ovat tilakonstruoituvia, niin
myös , ja
ovat tilakonstruoituvia.
Jokaisella rekursiivisella funktiolla r(n) on olemassa
tilakonstruoituva .
Todista, että jokaisella tilakonstruoituvalla
on voimassa sisältyvyys
(Vihje: Muodosta verkko, jonka solmut ovat simuloitavan
epädeterministisen koneen tilannekuvauksia.)