581336 Laskennan teoria (kevät 2006) Harjoitus 8 (28.-31.3.)
1. (a) Osoita, että jos A pmB ja B pmC, niin A pmC.
(b) Jos on osoitettu A pmB ja lisäksi tiedetään, että ongelma A on NP-täydellinen, niin mitä voidaan päätellä ongelmasta B?
(c) Jos on osoitettu A pmB ja lisäksi tiedetään, että ongelma B on NP-täydellinen, niin mitä voidaan päätellä ongelmasta A?
2. (a) Osoita, että jos A 2 P niin A pmB kaikilla B 62 f ;; g.
(b) Jos pätisi P = NP, niin mitkä kielet olisivat NP-täydellisiä?
3. Sanomme, että kaksi verkkoa G1 = (V1; E1) ja G2= (V2; E2) ovat isomorset, jos on olemassa bijektio f: V1 ! V2, jolle (u; v) 2 E1 jos ja vain jos (f(u); f(v)) 2 E2. Siis G1 ja G2 ovat isomorset, jos ne ovat solmujen nimiä lukuunottamatta sama verkko. Verkon G = (V; E) osaverkkoja ovat verkot G0 = (V0; E0), joilla V0 V ja E0 E.
Tehtävänä on osoittaa, että seuraava osaverkkoisomoraongelma (Subgraph Isomorphism, SI) on NP-täydellinen:
Annettu: kaksi suuntaamatonta verkkoa G1= (V1; E1) ja G2= (V2; E2)
Kysymys: onko verkko G1 isomornen verkon G2 jokin osaverkon kanssa, ts. onko olemassa U V2 ja bijektio f: V1! U, joille (f(u); f(v)) 2 E2 aina kun (u; v) 2 E1.
Tehdään tämä vaiheittain palautuksena luennolla esitetystä klikkiongelmasta (Clique), jonka NP-täydellisyys oletetaan tunnetuksi.
(a) Osoita, että SI 2 NP.
(b) Vielä pitää muodostaa palautus ongelmasta Clique ongelmaan SI. Kuvaa, minkä tyyppisiä arvoja tällainen palautus saa syötteenään ja millaisia palauttaa, ja mitä ehtoja sen pitää toteuttaa.
(c) Esitä varsinainen palautus ja osoita, että se toteuttaa kohdan (b) ehdot.
Voit merkitä tehtävän tehdyksi, vaikka et olisi keksinyt ratkaisua kohtaan (c).
4. Osoita, että jos SAT 2 P, niin on olemassa polynomisessa ajassa toimiva algoritmi, joka löy- tää annetulle toteutuvalle kaavalle (x1; : : : ; xn) sen toteuttavat muuttujien arvot (ts. jonon (v1; : : : ; vn) 2 f 0; 1 gn jolla (v1; : : : ; vn) = 1).
Vihje: jos (x1; x2; : : : ; xn) on toteutuva, niin ainakin toinen kaavoista (0; x2; : : : ; xn) ja (1; x2; : : : ; xn) on toteutuva.
