581336 Laskennan teoria (kevät 2006) Harjoitus 9 (4.-7.4.)
1. (a) Onko universaalikieli Lu NP-täydellinen? Entä NP-kova? Perustele.
(b) Onko seuraava ongelma ratkeava:
Annettu: Turingin kone M
Kysymys: onko kieli L(M) NP-täydellinen Perustele.
2. Muodosta propositiologiikan kaavaa
((x1_ x3_ :x4) ^ x2) _ (:x3^ (:x1_ x4)) _ (x1^ x3)
vastaava CNF-kaava luentojen sivuilla 233234 esitetyllä menetelmällä, ja tästä edelleen 3-CNF- kaava sivuilla 241243 esitetyllä konstruktiolla. Alkuperäinen kaava on toteutuva; eräs sen toteut- tava muuttujien arvoasetus on (x1; x2; x3; x4) = (0; 1; 1; 0). Millaiset toteuttavat arvoasetukset tästä saadaan muunnetuille kaavoille?
3. Osoita, että klikkiongelma (Clique) on NP-täydellinen. Voit olettaa tunnetuksi, että riippuma- ton joukko -ongelma (IS) on NP-täydellinen.
Vihje: Solmujoukko U V on riippumaton verkossa (V; E), jos ja vain jos U on klikki komple- menttiverkossa (V; E). (Tässä (u; v) 2 E joss (u; v) 62 E.)
4. Osoita, että seuraava joukkopeiteongelma (Set Cover) on NP-täydellinen:
Annettu: perusjoukko X = f x1; : : : ; xng, kokoelma R = f S1; : : : ; Skg osajoukkoja Si X sekä luonnollinen luku c
Kysymys: sisältääkö kokoelma R kokoa c olevan joukkopeitteen; ts. onko olemassa I f 1; : : : ; k g, jolla [i2ISi= X ja jIj = c.
Voit pitää tunnettuna, että solmupeiteongelma (Vertex Cover) on NP-täydellinen.
Vihje: Aseta X vastaamaan solmupeiteongelman kaarten joukkoa E ja jokaista solmua v 2 V vastaamaan sopivasti valittu joukko Si.
Tehtävissä 3 ja 4 jaa todistus vaiheisiin samoin kuin edellisen kerran tehtävässä 3. Voit merkitä teh- tävän tehdyksi, vaikka viimeinen vaihe olisi tekemättä.
