581336 Laskennan teoria (kevät 2006) Harjoitus 9, ratkaisuja
1. (a) Universaalikieli Lu on NP-kova mutta ei NP-täydellinen. Kielen NP-kovuus osoitetaan va- litsemalla mielivaltainen NP-täydellinen kieli A ja muodostamalla polynominen palautus f : A pm Lu, missä f(x) = w111x ja w on jonkin kielen A tunnistavan Turingin koneen koodi. Kieli Lu ei sen sijaan ole NP-täydellinen, sillä luokka NP on luokan REC osajouk- ko. Koska Lu ei ole rekursiivinen kieli, ei se myöskään kuulu luokkaan NP, mikä taas olisi NP-täydellisyyden edellytys.
(b) Annettu ongelma ei ole ratkeava. Kysymys on semanttisesta ominaisuudesta, sillä ongelma käsittelee syötteenä saadun Turingin koneen tunnistamaa kieltä. Ominaisuus on epätrivi- aali, sillä a-kohdan nojalla universaalikieli Luei ole NP-täydellinen, kun taas propositiolo- giikan kaavojen toteutuvuusongelma SAT on. Näin ollen ongelma on Ricen lauseen nojalla ratkeamaton.
2. Tarkasteltavana on siis CNF-kaavojen 1, 2 ja 3 disjunktio, missä 1 = (x1_ x3_ :x4) ^ x2
2 = :x3^ (:x1_ x4) 3 = x1_ x3:
Muodostetaan ensin disjunktiota 1_ 2 vastaava CNF-kaava
1= (y1_ x1_ x3_ :x4) ^ (y1_ x2) ^ (:y1_ :x3) ^ (:y1_ :x1_ x4);
missä on otettu käyttöön uusi muuttuja y1. Sovelletaan muunnosta edelleen kaavaan 1_ 3, jolloin lisäämällä muuttuja y2saadaan
(y1_y2_x1_x3_:x4)^(y1_y2_x2)^(:y1_y2_:x3)^(:y1_y2_:x1_x4)^(:y2_x1)^(:y2_x3):
Tämä on siis haluttu CNF-kaava. Muunnetaan edelleen jokainen klausuuli 3-CNF-kaavaksi:
y1_ y2_ x1_ x3_ :x4 7! (y1_ y2_ z1) ^ (:z1_ x1_ z2) ^ (:z2_ x3_ :x4) y1_ y2_ x2 7! y1_ y2_ x2
:y1_ y2_ :x3 7! :y1_ y2_ :x3
:y1_ y2_ :x1_ x4 7! (:y1_ y2_ z3) ^ (:z3_ :x1_ x4) :y2_ x1 7! (:y2_ x1_ z4) ^ (:y2_ x1_ :z4) :y2_ x3 7! (:y2_ x3_ z5) ^ (:y2_ x3_ :z5) ja lopulliseksi 3-CNF-kaavaksi saadaan
((y1_ y2_ z1) ^ (:z1_ x1_ z2) ^ (:z2_ x3_ :x4))
^ (y1_ y2_ x2)
^ (:y1_ y2_ :x3)
^ (:y1_ y2_ z3) ^ (:z3_ :x1_ x4)
^ (:y2_ x1_ z4) ^ (:y2_ x1_ :z4)
^ (:y2_ x3_ z5) ^ (:y2_ x3_ :z5):
Muuttujien arvot (x1; x2; x3; x4) = (0; 1; 1; 0) toteuttavat kaavan 1, mutta eivät kaavoja 2 tai 3, joten CNF-kaavan toteuttamiseksi näillä x-muuttujien arvoilla on valittava y1= 0 ja y2= 0.
Lopullisen 3-CNF-kaavan toteuttamiseksi pitää valita edelleen z1= 1 ja z2= 1; muuttujien z3, z4ja z5 arvoilla ei itse asiassa ole väliä.
3. Väite: Clique on NP-täydellinen.
Todistus: Täytyy siis osoittaa, että Clique 2 NP ja että B pmClique kaikilla B 2 NP.
Osoitetaan ensin Clique 2 NP laatimalla epädeterministinen Turingin kone, joka ratkaisee ongelman polynomisessa ajassa. Kone saa syötteenään verkon G = (V; E) ja luonnollisen luvun k, eli käytännössä jotenkin sopivasti koodatun parin hG; ki. Kone toimii seuraavasti:
(a) Tarkista syöte; jos se ei ole koodaus millään hG; ki, hylkää.
(b) Aseta U := ;.
(c) Toista jokaisella v 2 V : valitse epädeterministisesti joko U := U [ fvg tai U := U.
(d) Jos jUj < k, hylkää.
(e) Toista kaikilla u; v 2 U: jos (u; v) 62 E, hylkää.
(f) Hyväksy.
Selvästi kone hyväksyy syötteen jos ja vain jos on olemassa sellainen U V , että jUj k ja (u; v) 2 E kaikilla u; v 2 U. Polynominen aikavaatimuskin on selvä. Siis Clique 2 NP.
Osoitetaan sitten B pm Clique kaikilla B 2 NP. Polynomisten palautusten transitiivisuuden vuoksi riittää osoittaa C pm Clique jollakin NP-kovaksi tiedetyllä C. Riippumaton joukko - ongelma IS tiedetään NP-kovaksi.
Olkoon verkon G = (V; E) komplementtiverkko G = (V; (V V ) E). Muodostetaan palautus f : IS pmClique:
f(x) =
(hG; ki; jos x on koodaus jollakin hG; ki hG0; 2i; muuten,
missä G0 on jokin yksisolmuinen verkko. Nyt
x 2 IS , 9U V : jUj k ^ 8u; v 2 U : (u; v) 62 E
, 9U V : jUj k ^ 8u; v 2 U : (u; v) 2 (V V ) E , f(x) 2 Clique
Funktio f voidaan selvästi laskea polynomisessa ajassa: käydään läpi kaikki parit (u; v) 2 V V ja otetaan tulosverkkoon ne parit, joita ei löydy alkuperäisestä. Näinollen IS pmClique.
Ylläolevan perusteella Clique 2 NP ja B pm Clique kaikilla B 2 NP, joten Clique on
NP-täydellinen. 2
4. Osoitetaan joukkopeiteongelman olevan NP-täydellinen.
Aluksi osoitetaan joukkopeiteongelman kuuluvan luokkaan NP. Tämä tapahtuu esittämällä epä- deterministinen polynomisessa ajassa toimiva algoritmi, joka ratkaisee ongelman. Algoritmi
(a) muodostaa indeksijoukon I käymällä läpi arvot 1; : : : ; k ja valitsemalla epädeterministisesti jokaisella i, päteekö i 2 I;
(b) tarkistaa, päteekö jIj = c, ja hylkää jos näin ei ole;
(c) muodostaa yhdisteen Y =S
i2ISi sekä
(d) tarkistaa, päteekö Y = X, ja vastaa sen mukaan.
Esitetty epädeterministinen algoritmi toimii selvästi polynomisessa ajassa ja ratkaisee joukko- peiteongelman, joten joukkopeiteongelma kuuluu luokkaan NP.
Seuraavaksi osoitetaan joukkopeiteongelman NP-kovuus tekemällä polynominen palautus NP- täydelliseksi tunnetusta solmupeiteongelmasta siihen. Solmupeiteongelmassa syötteenä saadaan
2
verkko G = (V; E) ja luonnollinen luku c ja kysytään, onko olemassa kokoa c olevaa solmujoukkoa U V niin, että verkon jokaisesta kaaresta vähintään toinen pää kuuluu joukkoon U.
Merkitään solmupeiteongelman mukaista kieltä VC ja joukkopeiteongelman mukaista kieltä SC.
Tavoitteena on muodostaa deterministisesti polynomisessa ajassa laskettava funktio f, jolla pätee ((V; E); c) 2 V C () f((V; E); c) 2 SC:
Funktio toimii seuraavasti:
Perusjoukoksi valitaan kaarten joukko E.
Osajoukkokokoelmaksi valitaan fSu j u 2 V g, missä osajoukot Su = f(v; w) 2 E j u = v tai u = wg sisältävät solmuun u liittyvät kaaret.
Joukkopeitteen kooksi valitaan solmupeitteen koko c.
(Jos syöte ei ole oikeaa muotoa, palautus tuottaa mielivaltaisen merkkijonon, joka ei myöskään ole oikeaa muotoa.)
Funktio voidaan selvästikin laskea deterministisesti polynomisessa ajassa. Kysymyksessä on pa- lautus solmupeiteongelmasta joukkopeiteongelmaan, sillä solmujoukko U on solmupeite jos ja vain jos joukkoon U kuuluu vähintään toinen pää jokaisesta verkon kaaresta eli jos ja vain jos kaikki verkon kaaret kuuluvat kokoelman fSuj u 2 Ug johonkin osajoukkoon Su eli jos ja vain jos tämä kokoelma on joukkopeite.
Näin ollen joukkopeiteongelma on NP kova, ja koska sen aikaisemmin osoitettiin kuuluvan luok- kaan NP, on se myös NP-täydellinen.
3
