581336 Laskennan teoria (kevät 2006) Harjoitus 8, ratkaisuja
1. (a) Lause: Jos A pmB ja B pmC niin A pmC.
Todistus: Olkoon f : A pm B; siis x 2 A jos ja vain jos f(x) 2 B, ja lisäksi jokin deterministinen Turingin kone M laskee funktion f ajassa O(nk) jollain k. Vastavasti olkoon g : B pmC, ja N deterministinen Turingin kone joka laskee funktion g ajassa O(n`).
Olkoon h = g f; ts. h(x) = g(f(x)) kaikilla x. Nyt
x 2 A , f(x) 2 B koska f palautus
, g(f(x)) 2 C koska g palautus
, h(x) 2 C:
Lisäksi funktio h voidaan laskea seuraavasti:
i. simuloi koneen M laskentaa kunnes se pysähtyy ii. siirrä nauhapää nauhalla olevan merkkijonon alkuun iii. simuloi koneen N laskentaa
Tarkastellaan tätä laskentaa syötteellä x, ja merkitään y = f(x). Vaihe 1 kestää O(jxjk) askelta ja sen jälkeen koneen M määritelmän mukaan nauhalla on y. Erityisesti vaihe 2 vie O(jyj) = O(jxjk) askelta. Vaihe 3 vie vastaavasti O(jyj`) = O((jxjk)`) askelta ja sen jälkeen nauhalla on g(y) = h(x). Siis h saadaan lasketuksi ajassa O(jxjk+ jxjk+ jxjk`) = O(jxjk`) joten h on polynominen palautus ongelmasta A ongelmaan C. 2 (b) Oletetaan, että on osoitettu A pm B ja että lisäksi tiedetään ongelman A olevan NP- täydellinen. Erityisesti tiedetään siis, että C pm A kaikilla C 2 NP. Edellä todistetun lauseen perusteella tällöin myös C pm B kaikilla C 2 NP. Voidaan siis päätellä, että ongelma B on NP-kova.
(c) Oletetaan, että on osoitettu A pm B ja että lisäksi tiedetään ongelman B olevan NP- täydellinen. Erityisesti tiedetään siis, että B 2 NP. Lemman 3.2 (s. 204) perusteella voidaan päätellä, että A 2 NP.
2. (a) Lause: Jos A 2 P ja B 62 f;; g, niin A pmB.
Todistus: Oletuksen mukaan on olemassa merkkijonot a 2 B ja b 2 B. Seuraava funktio f on selvästi palautus joukosta A joukkoon B:
f(x) =
(a jos x 2 A b jos x 62 A
Lisäksi, kun oletetaan että deterministinen Turingin kone M hyväksyy kielen A polynomi- sessa ajassa, f voidaan laskea polynomisessa ajassa seuraavasti:
i. Simuloi koneen M laskentaa.
ii. Jos M hyväksyi, niin tyhjennä nauha, kirjoita sille a ja hyväksy.
iii. Jos M hylkäsi, niin tyhjennä nauha, kirjoita sille b ja hyväksy.
Huomaa, että M pysähtyy kaikilla syötteillä polynomisessa ajassa. Siis f : A pmB. 2 (b) Jos B = ; ja A pm B, niin polynomisen palautuksen määritelmästä seuraa suoraan että A = ;. Samoin jos B = ja A pmB, niin A = (kun puhutaan aakkoston kielistä).
Koska NP sisältää muitakin kieliä kuin ; ja , ei kumpikaan näistä kielistä voi olla NP- täydellinen.
Olkoon toisaalta B 62 f;; g. Edellisen kohdan perusteella A pmB kaikilla A 2 P. Olete- taan nyt lisäksi P = NP. Siis erityisesti A pmB kaikilla A 2 NP. Siis B on NP-täydellinen kunhan lisäksi B 2 NP eli siis B 2 P.
Oletuksen P = NP vallitessa NP-täydellisiä ovat siis kaikki luokan P kielet paitsi ; ja .
3. (a) Osoitetaan, että SI 2 NP laatimalla ongelmalle epädeterministinen polynomisessa ajassa toimiva Turingin kone:
i. Tarkista syöte; jos se ei ole muotoa hG1; G2i, hylkää.
ii. Toista jokaisella u 2 V1: valitse epädeterminisesti jokin v 2 V2 ja aseta f(u) = v.
iii. Toista kaikilla u; v 2 V1: jos u 6= v ja f(u) = f(v), hylkää.
iv. Toista kaikilla u; v 2 V1: jos (u; v) 2 E1 mutta (f(u); f(v)) 62 E2, hylkää.
v. Hyväksy.
Polynominen aikavaatimus on selvä. Kohdassa ii arvataan vaadittu f (joukko U V2
muodostuu valituista solmuista v 2 V2). Kohta iii varmistaa, että f on injektio ja siten myös bijektio (koska f on automaattisesti surjektio). Kohta iv tarkistaa ehdon (u; v) 2 E1 jos ja vain jos (f(u); f(v)) 2 E2. Siispä kone hyväksyy syötteen x jos ja vain jos x 2 SI.
(b) Tarkastellaan ensin asiaa formaalien määritelmien kannalta. Olkoon Clique-tapaukset koo- dattu jonkin aakkoston merkkijonoina ja SI-tapaukset vastaavasti aakkoston merkki- jonoina (jolloin voi hyvin olla = ). Käytetetään merkintää hG; ki merkkijonolle, joka jollain sovitulla tavalla koodaa verkon G ja luonnollisen luvun k aakkoston merkkijonok- si. Sovitusta koodauksesta riippuen tyypillisesti läheskään kaikki x 2 eivät ole muotoa hG; ki, ts. eivät muodosta validia koodia millekään verkolle G ja luonnolliselle luvulle k.
Vastaavasti olkoon hG1; G2i aakkoston merkkijono, joka koodaa kaksi verkkoa, G1ja G2. Siis Clique = f hG; ki j verkossa G on k solmun klikki g ;
ja vastaavasti
IS = f hG1; G2i j verkossa G2on verkon G1 kanssa isomornen osaverkko g : Palautus g : Clique pm SI on nyt funktio ! , eli saa syötteenään aakkoston merkkijonon x ja palauttaa aakkoston merkkijonon g(x). Palautuksen on toteutettava
ehto x 2 Clique , g(x) 2 SI
ja lisäksi sen on oltava laskettavissa polynomisessa ajassa syötteen x pituuden suhteen.
Käytännössä yleensä ajattelemme, että klikkiongelman tapauksia ovat muotoa hG; ki ole- vat merkkijonot, eikä meitä kiinnosta, mitä tapahtuu muunlaisille merkkijonoille x 2 . Sanomme, että palautusfunktion syötteitä ovat muotoa hG; ki olevat merkkijonot, ja tulos- teita muotoa hG1; G2i olevat merkkijonot. Tällöin tarkoitamme, että jos x ei ole muotoa hG; ki, niin g(x) 2 on jokin kiinteä merkkijono, joka ei ole muotoa hG1; G2i (jolloin erityisesti g(x) 62 SI). Funktion g pitää olla laskettavissa polynomisessa ajassa, ja kun g(hG; ki) = hG1; G2i, niin verkolla G2 pitää olla verkon G1 kanssa isomornen osaverkko täsmälleen niissä tapauksissa, joissa verkossa G on k solmun klikki.
Vielä havainnollisempaa on jättää koko koodausvaiheen huomiotta ja sanoa, että palautus- funktion g syötteenä on verkko G ja luonnollinen luku k ja tulosteena verkot G1 ja G2. Muodollisesti tällä tarkoitetaan samaa kuin edellä, eli jos x on muotoa hG; ki, niin g(x) on muotoa hG1; G2i.
(c) Olkoon g funktio
g(hG; ki) =
(hKk; Gi jos k jV j, missä G = (V; E);
hK2; K1i muuten;
missä Kk on k-solmuinen täydellinen verkko.
Olkoon x = hG; ki. Jos k > jV j, pätee x 62 Clique ja g(x) 62 SI. Jos k jV j, x 2 Clique , verkossa G on vähintään k solmun klikki
, verkko Gk on isomornen jonkin verkon G osaverkon kanssa , g(x) 2 SI;
2
joten g toteuttaa ehdon x 2 Clique , g(x) 2 SI kaikilla x. Polynomisen laskenta-ajan takaa se, että muodostettavissa täydellisissä verkoissa on aina joko vakiomäärä solmuja tai korkeintaan yhtä monta solmua kuin syöteverkossa. (Ilman funktion määrittelyssä olevaa ehtoa k jV j voitaisiin joutua kirjoittamaan syötteen pituuteen nähden eksponentiaali- sen pitkä täydellisen verkon esitys.) Siis g : Clique pmSI. 2 4. Sovelletaan vastaavaa ratkaisuideaa kuin Hamiltonin kehään luennoilla (sivu 184). Oletetaan, et- tä SAT 2 P , jolloin jokin polynomisessa ajassa toimiva algoritmi A ratkaisee sen. Muodostetaan algoritmia A hyväksi käyttäen algoritmi, joka löytää polynomisessa ajassa kaavalle (x1; : : : ; xn) ratkaisun.
Olkoon (xi:= 0) kaava, jossa jokainen muuttujan xiesiintymä kaavassa on korvattu epätoden symbolilla 0. Vastaavasti kaavassa (xi:= 1) jokainen muuttujan xiesiintymä on korvattu toden symbolilla 1. Algoritmi toimii seuraavasti:
Jos A() = 0, palauta ().
Toista arvoilla i := 1 : : : n
Jos A((xi:= 0)) = 1, aseta vi:= 0 ja := (xi:= 0).
Muuten aseta vi:= 1 ja := (xi:= 1).
Palauta (v1; : : : ; vn).
Algoritmi toimii selvästi polynomisessa ajassa, sillä siinä suoritetaan korkeintaan n + 1 kertaa algoritmi A ja tehdään lisäksi (n) triviaalia operaatiota.
Algoritmi toimii myös oikein. Se perustuu havaintoon, että kaava jos on toteutuva, on sille kaikilla xi olemassa ratkaisu, jossa xi = 0 tai ratkaisu, josssa xi = 1. Algoritmi käy kaikki kaavan muuttujat järjestyksessä läpi tarkistaen, onko kaava toteutuva, jos ensimmäinen vapaa muuttuja xisaa arvon 0. Jos näin on, on kaavalla ratkaisu, jossa xi= 0, jolloin voidaan rajoittua tarkastelemaan tällaisia ratkaisuehdokkaita. Muussa tapauksessa sillä on oltava ratkaisu, jossa xi = 1, jolloin vastaavasti voidaan rajoittua näihin ratkaisuihin. Kun kaikki vapaat muuttujat on korvattu nollilla tai ykkösillä, on kaavalle löydetty ratkaisu.
3
