Tentti 23.5.1995

Kirjoita jokaiseen paperiin

- nimi, osasto, vsk

- opintokirjan numero

- Tik-79.153 Alg. ja lasket. tentti 23.5.95

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. Mitkä seuraavista ovat kompleksisuus- eli vaativuusmittoja:

a) Ci(x) = 0, kaikilla i, x

b) Ci(x) = Mi(x), jos i on parillinen, muuten theta-i,(x):n laskemiseen vaadittavien askelien määrä.

3. 2-väritettävyysongelmassa (2-COLORABILITY) on määritettävä voidaanko annettu verkko "värittää" käyttäen vain kahta "väriä". Osoita, että 2-väritettävyysongelma on luokassa P.

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

a) "Jump" operaatio

b) Speedup-teoreema

c) Turing-redusoituvuus (<=T)

5. Määrittele oraakkeli ja selitä miksi ja mihin kyseistä käsitettä tarvitaan.