581336 Laskennan teoria (kevät 2006) Harjoitus 10 (11.12.4. ja 21.4.)
Pääsiäisloman aikana 13.19.4. kurssilla ei ole luentoja eikä laskuharjoituksia.
1. Tarkastellaan luennolla (s. 245248) esitettyä palautusta f: 3SAT pmIS. Jos on kaava (x1_ x2_ x3) ^ (x1_ :x2_ :x3) ^ (:x1_ :x2_ x3) ^ (:x1_ x2_ :x3);
niin mikä on f()? Millä muuttujien arvokombinaatioilla toteutuu? Mitkä ovat palautuksessa konstruoidun verkon suurimmat riippumattomat joukot?
2. Osoita, että Hamiltonin kehä -ongelma HC on NP-täydellinen. Voit pitää tunnettuna, että suun- nattujen verkkojen Hamiltonin kehä -ongelma DHC on NP-täydellinen. (Vihje: tämä on kurssi- kirjan Theorem 10.23.)
3. Verkon G = (V; E) Hamiltonin polku on polku, joka käy verkon jokaisessa solmussa tasan kerran;
erotukseksi Hamiltonin kehästä se ei enää palaa lähtösolmuunsa. Muodollisesti Hamiltonin polku on siis solmujono v1; : : : ; vn, missä n = jV j, f v1; : : : ; vng = V ja (vi; vi+1) 2 E kun 1 i n 1.
Tämä määritelmä soveltuu suoraan sekä suunnatuille että suuntaamattomille verkoille.
Suunnattu Hamiltonin polku -ongelma on seuraava:
Annettu: suunnattu verkko G
Kysymys: onko verkossa G Hamiltonin polku.
Osoita, että ongelma on NP-täydellinen. Voit käyttää hyväksi tietoa, että suunnattu Hamiltonin kehä on NP-täydellinen. (Vihje: halkaise jokin solmu v kahdeksi solmuksi v0 ja v00 ja jaa siihen liittyvät kaaret siten, että syntyvän verkon Hamiltonin polkujen on pakko alkaa kaaresta v0 ja päättyä solmuun v00.)
4. Olkoon f joukossa f 2; 3; 4; : : : g määritelty funktio, jolla f(x) on luvun x pienin alkutekijä. Siis esim. f(13) = 13 koska 13 on alkuluku, f(15) = 3 koska 15 = 3 5 ja f(1573) = 11 koska 1573 = 11 11 13. Osoita, että jos P = NP, niin funktio f voidaan laskea polynomisessa ajassa.
Yleisluontoinen vihje: Koska NP on luokka päätösongelmia ja funktion f laskeminen on etsintä- ongelma, sinun pitää palauttaa f jonoksi päätösongelmia samaan tapaan kuin esim. harjoituk- sen 8 tehtävässä 4. Ongelmana on löytää sopiva luokan NP päätösongelma.
