581336 Laskennan teoria (kevät 2006) Harjoitus 10, ratkaisuja

581336 Laskennan teoria (kevät 2006) Harjoitus 10, ratkaisuja

1. Annetulla kaavalla

= (x₁_ x₂_ x₃) ^ (x₁_ :x₂_ :x₃) ^ (:x₁_ :x₂_ x₃) ^ (:x₁_ x₂_ :x₃) palautusfunktio antaa f() = hG; ki, missä k = 4 ja G on verkko

x1 x1

x2 x2

x3 x3

:x1 :x1

:x2 :x2

:x3 :x3

,

, ,

,

(solmuihin on lisätty muuttujasymbolit palautuksen havainnollistamiseksi).

Kaava toteutuu, kun muuttujien arvot (x1; x2; x3) ovat joko (1; 1; 1), (1; 0; 0), (0; 1; 0) tai (0; 0; 1). Jos verkon solmut nimetään luennolla esitetyn mukaisesti vi;r, i = 1; : : : ; 4, r = 1; 2; 3, niin vastaavat riippumattomat joukot ovat f v1;1; v2;1; v3;3; v4;2g, f v1;1; v2;1; v3;2; v4;3g, f v1;2; v2;3; v3;1; v4;1g ja f v1;3; v2;2; v3;1; v4;1g.

2. Osoitetaan suuntaamattomien verkkojen Hamiltonin kehä -ongelman HC olevan NP-täydellinen palauttamalla se NP-täydelliseksi tunnettuun suunnattujen verkkojen vastaavaan ongelmaan DHC ja päinvastoin.

Hamiltonin kehä -ongelmassa kysytään, onko annetussa verkossa sykliä, joka käy jokaisessa ver- kon solmussa täsmälleen kerran. Koska suuntaamaton verkko on samalla suunnattu verkko, jossa on kaari (u; v) jos ja vain jos siinä on kaari (v; u), on palautus f : HC ^p_mDHC yksinkertaisesti identtinen kuvaus.

Muodostetaan seuraavaksi palautus g : DHC ^p_mHC. Suuntaamattomaan verkkoon luodaan jo- kaista suunnatun verkon solmua v kohti kolme solmua: tulosolmu v₁, sisäsolmu v₂ja lähtösolmu v3. Jokainen suunnatun verkon kaari (u; v) kuvataan puolestaan kaareksi solmua u vastaavasta lähtösolmusta u3 solmua v vastaavaan tulosolmuun v1. Lisäksi jokaiseen kolmikkoon v1; v2; v3

lisätään kaaret (v1; v2) ja (v2; v3). Tällainen verkko voidaan selvästikin muodostaa determinis- tisesti polynomisessa ajassa. Merkitään nyt g(V; E) = (V⁰; E⁰). (Jos syöte ei kuvaa suunnattua verkkoa, g tuottaa mielivaltaisen merkkijonon, joka ei kuvaa suuntaamatonta verkkoa.)

Kysymys on palautuksesta DHC ^p_m HC. Jos nimittäin suunnatussa verkossa (V; E) on Ha- miltonin kehä, löytyy sellainen myös suuntaamattomasta verkosta (V⁰; E⁰). Suuntaamattoman verkon kehässä käydään kolmikot v₁; v₂; v₃läpi samassa järjestyksessä kuin niitä vastaavat suun- natun verkon solmut. Kunkin kolmikon sisällä puolestaan käydään ensin tulosolmussa v₁, sitten sisäsolmussa v₂ ja lopuksi lähtösolmussa v₃, minkä jälkeen siirrytään seuraavaan kolmikkoon.

Oletetaan nyt, että suuntaamattomassa verkossa (V⁰; E⁰) on Hamiltonin kehä. Koska jokaisesta sisäsolmusta on kaaret vain saman kolmikon tulo- ja lähtösolmuihin, täytyy koko kolmikko käydä

läpi kerralla. Niinpä jokaista suunnatun verkon solmua v 2 V kohti on suuntaamattoman ver- kon Hamiltonin kehässä joko jakso (v1; v2; v3) tai (v3; v2; v1). Lisäksi koska kolmikoiden väliset kaaret yhdistävät ainoastaan lähtösolmuja tulosolmuihin, täytyy syklissä peräkkäiset kolmikot ja siten kaikki kolmikot käydä läpi samassa järjestyksessä. Koska sykli voidaan käydä läpi yhtä hyvin etu- tai takaperin, voidaan järjestyksen olettaa olevan (v1; v2; v3). Nyt suunnatun ver- kon Hamiltonin kehä saadaan käymällä solmut läpi samassa järjestyksessä kuin niitä vastaavat kolmikot suuntaamattomassa verkossa. Tämä onnistuu, sillä jokaista suuntaamattoman verkon kaarta (u3; v1) kohti on suunnatussa verkossa kaari (u; v).

Funktio f on siis osoitettu polynomiseksi palautukseksi HC ^p_mDHC ja funktio g palautukseksi DHC ^p_m HC. Koska DHC on NP-täydellinen, on näiden palautusten seurauksena myös HC sellainen.

3. Olkoon DHP tehtävässä määritelty suunnaatujen verkkojen Hamiltonin polku -ongelma.

Väite: DHP on NP-täydellinen.

Todistus: Osoitetaan, että DHP 2 NP ja DHC ^p_mDHP, missä DHC on suunnattujen verkkojen Hamiltonin kehä -ongelma. Koska DHC on NP-täydellinen, väite seuraa.

Ongelma DHP voidaan ratkaista seuraavalla epädeterministisellä algoritmilla, joka selvästi toimii polynomisessa ajassa:

(a) Olkoon syöte G = (V; E). Jos syöte ei ole tätä muotoa, niin hylkää.

(b) Aseta U = V ja n = jV j.

(c) Toista arvoilla i = 1; : : : ; n:

i. Valitse epädeterministisesti jokin u 2 U.

ii. Aseta w[i] = u.

iii. Päivitä U := U f u g.

(d) Toista arvoilla i = 1; : : : ; n 1: jos (w[i]; w[i + 1]) 62 E, niin hylkää.

(e) Hyväksy.

Olkoon G = (V; E) suunnattu verkko, missä jV j = n ja V = f v₁; : : : ; v_ng. Määritellään suunnat- tu verkko f(G) = (V⁰; E⁰), missä V⁰ = f v0; v1; : : : ; vng ja joukkoon E⁰ tulee seuraavat kaaret:

jos (vi; vn) 2 E jollain 1 i n 1, niin (vi; vn) 2 E⁰, jos (vn; vi) 2 E jollain 1 i n 1, niin (v0; vi) 2 E⁰ ja jos (vi; vj) 2 E joillain 1 i; j n 1, niin (vi; vj) 2 E⁰. Selvästi kuvaus f voidaan laskea polynomisessa ajassa.

Olkoon (w₁; : : : ; w_n) Hamiltonin kehä verkossa G. Yleisyyttä rajoittamatta voidaan valita solmu- jen numerointi niin, että w_n = v_n. Joukossa E on siis kaari (w_i; w_i+1) kaikilla i = 2; : : : ; n 1 ja li- säksi kaaret (w_{n 1}; w_n) = (w_{n 1}; v_n) ja (w_n; w₁) = (v_n; w₁). Joukossa E⁰ on siis kaari (w_i; w_i+1) kaikilla i = 1; : : : ; n 2 ja lisäksi kaaret (w_{n 1}; v_n) ja (v₀; w₁). Siis (v₀; w₁; : : : ; w_{n 1}; v_n) on Hamiltonin polku verkossa (V⁰; E⁰) = f(G).

Olkoon toisaalta (w₀; w₁; : : : ; w_n) Hamiltonin polku verkossa f(G). Koska solmuun v₀ ei tule eikä solmusta v_n lähde kaaria, on oltava w₀ = v₀ ja w_n = v_n. Tarkastelemalla taas joukon E⁰ määritelmää nähdään, että (w1; : : : ; wn) on Hamiltonin kehä verkossa G.

Siis G 2 DHC jos ja vain jos f(G) 2 DHP, joten f on polynominen palautus DHC ^p_mDHP. 2 4. Väite: Jos P = NP, niin funktio f : f2; 3; 4; : : : g ! fn 2 N j n on alkulukug, f(x) = luvun x

pienin alkutekijä, voidaan laskea polynomisessa ajassa.

2

Todistus. Käytetään luokkaan NP kuuluvaa päätösongelmaa FACT: Annettu luonnolliset luvut a ja b, ja kysytään Onko luvulla b tekijä d, jolla 1 < d a?. Tätä päätösongelmaa vastaa kieli (merkintä djb tarkoittaa b on jaollinen d:llä):

fha; bi j 9d : 1 < d a ^ djbg:

Nyt saadaan seuraava algoritmi funktion f laskemiseksi: etsitään pienin alkutekijä binäärihaulla (syötteenä luku x 2):

(a) Aseta a := 2, y := x.

(b) Toista, kunnes a = y:

i. Aseta k := b(a + y)=2c.

ii. Jos hk; xi 2 FACT, niin aseta y := k, muuten aseta a := k + 1.

(c) Palauta a.

Algoritmin oikeellisuus: kohdan (b) silmukka säilyttää invariantin a d y, missä d on luvun x pienin alkutekijä. Aluksi (a = 2, y = x) invariantti pätee triviaalisti. Jos silmukan alussa a < y ja invariantti on voimassa, niin seuraavaksi joko

hk; xi 2 FACT, jolloin on tekijä k; tällöin a d k tai hk; xi 62 FACT, jolloin ei ole tekijää k; tällöin k + 1 d y.

Lopuksi d = a = y: jos jossain vaiheessa olisi a > y, olisi silmukan edellisen suorituskerran alussa pitänyt olla a = y, jolloin silmukkaa ei olisi enää suoritettu.

Aikavaatimus: silmukan sisältö (kohdat i. ja ii.) suoritetaan O(log x) kertaa, ja silmukan sisällön aikavaatimus on oletuksen P = NP mukaan polynominen syötteen pituuden O(log x) suhteen.

Näinollen koko algoritmin aikavaatimus on polynominen syötteen pituuden O(log x) suhteen. 2

3