581336 Laskennan teoria (syksy 2003) Harjoitus 6 (25.28.11.2003)

581336 Laskennan teoria (syksy 2003) Harjoitus 6 (25.28.11.2003)

1. Todista seuraava:

Lause: Olkoot f jag funktioitaN→R⁺. Jos raja-arvo

n→∞lim f(n) g(n)

on nolla, niin f = o(g). Jos raja-arvo on ∞, niin g = o(f). Jos raja-arvo on jokin positiivinen reaaliluku, niinf = Θ(g).

(Huom. raja-arvo ei välttämättä ole määritelty, jolloin tämä ei sano mitään.) 2. Todista seuraavat kertaluokkien perusominaisuudet:

(a) log_an=o(n^b)kaikilla a >1,b >0 (b) n^a =o(2^bn)kaikilla a, b >0

(c) jospon astettakoleva polynomi niinp(n) = Θ(n^k)

3. Olkoonf(n) =n^lnn kaikillan. Osoita, ettän^k =o(f(n))kaikillak >0jaf(n) =o(2^an)kaikilla a >0.

4. Osoita, että jos SAT ∈ P niin on olemassa polynomisessa ajassa toimiva algoritmi joka löy- tää annetulle toteutuvalle kaavalle φ(x1, . . . , xn) sen toteuttavat muuttujien arvot (ts. jonon (v₁, . . . , v_n)∈ {0,1}ⁿ jollaφ(v₁, . . . , v_n) = 1).

Vihje: jos φ(x₁, x₂, . . . , x_n) on toteutuva, niin ainakin toinen kaavoista φ(0, x₂, . . . , x_n) ja φ(1, x₂, . . . , x_n)on toteutuva.

5. Osoita ettäNP on suljettu leikkausten ja yhdisteiden suhteen, ts. josA ∈NP jaB ∈NP niin A∩B ∈NPjaA∪B∈NP. Voitko sanoa mitään komplementoinnista?

6. Osoita, että seuraavat ongelmat kuuluvat luokkaanNP: Riippumaton joukko (Independent Set, IS)

Annettu: Suuntaamaton verkkoG= (V, E), luonnollinen lukuk

Kysymys: Onko olemassa solmujoukko U ⊆ V jolla |U| ≥ k ja minkään kahden joukossaU olevan solmun välillä ei ole kaarta (ts.E∩(U×U) =∅)

Ositus (Partition, PARTITION)

Annettu: jono(a₁, . . . , a_n)luonnollisia lukuja Kysymys: onko olemassa A⊆ {1, . . . , n} jolla

X

i∈A

a_i=X

i6∈A

a_i