Tentti 14.8.1995

Kirjoita jokaiseen paperiin

- nimi, osasto, vsk

- opintokirjan numero

- Tik-79.153 Alg. ja lasket. tentti 14.8.1995

1. Olkoon R(x,t) prim. rek. predikaatti.

g(x,y) = max R(x,t), jos tällainen t löytyy, muulloin g(x,y)=0.

t<y

Osoita, että g(x,y) on prim. rekursiivinen.

2. Olkoon C mielivaltainen kompleksisuusmitta. Osoita, että on olemassa rekursiivinen funktio t, jolle pätee

theta-i(x) < t(x,Ci(x)) melkein kaikkialla (a.e.)

3. Osoita, että, jos C on kompleksisuusmitta ja

Di(x) = {Ci(x), jos i kuuluu A:han

{0,jos i ei kuulu A:han

niin D on kompleksisuusmitta. A on äärellinen joukko siten, että theta-i; on määritelty koko luonnollisten lukujen joukossa (theta-i on totaalinen), kun i kuuluu A:han.

4 Selitä tai määrittele seuraavat käsitteet:

a) Rekursiivinen joukko

b) P, NP ja NP-täydellinen, mikä on näiden keskinäinen suhde.

c) Moniredusoituvuus (<=m)

5. a) Selitä Speedup-teoreeman sisältö ja esitä esimerkki sen soveltamisesta.

b) Mikä on laskettavuuden teorian suhde käytäntöön