581336 Laskennan teoria (kevät 2006) Harjoitus 7, ratkaisuja
1. Osoitetaan ensin, että nk = O(2cn) 8c < 0; k > 0. Määritelmän mukaan pitää siis osoittaa, että 9d > 0; n0 s.e. n > n0) nk d2cn. Pyritään ensin muuttamaan implikaation oikea puoli enemmän annettua lausetta muistuttavaan muotoon. Tarkastellaan ensin, miten 2cn voidaan esittää e:tä kantalukuna käyttäen:
2cn= eln 2cn = elog2 2cnlog2 e = elog2 ecn = (en)log2 ec Tätä käyttäen voidaan ehto muuntaa sopivampaan muotoon:
nk d2cn, nk d(en)log2 ec , nk log2 ec dlog2 ec en Tehtävänmäärittelyssä oli annettu seuraava lause:
n!1lim np en = 0;
eli
8p; > 0 9n00s.e. np
en < ; kun n > n00:
Valitaan = 1 ja p = k logc2e. Lauseen mukaan voidaan valita sellainen n00, että kaikilla n > n00 pätee nenp < . Valitaan nyt d = 1 ja n0= n00. Tällöin kaikilla n > n0on voimassa:
np
en < , nk log2 ec < dlog2 ec en;
siis haluttu ehto täyttyy valituilla d ja n0. 2
Osoitetaan seuraavaksi, että 2cn6= O(nk) 8c < 0; k > 0. Tämän todistamiseksi tehdään vastao- letus: 9c > 0; k > 0; d > 0; n0 s.e. n > n0) 2cn dnk.
Muutetaan taas ehto sopivampaan muotoon:
2cn dnk , nk d 1(en)log2 ec , nk log2 ec d log2 ec en
Valitaan = d log2 ec ja p = k logc2e. Lause ) 9n00 : nk log2 ec < d log2 ec en, kun n > n0o. Valitaan n = max(n0; n00) + 1. Nyt n > n0, mutta vastaoletuksen implikaation oikea puoli ei päde, joten saadaan ristiriita. Vastaoletus ei siis voi päteä, joten väite pätee. 2 Todistetun lauseen perusteella voidaan päätellä, että P E. Oletetaan, että L 2 P , siis L = L(M) jollain deterministisellä M, jonka aikavaativuus on O(nk) jollain k. Todistetun lauseen perusteella nk = O(2n), joten M:n aikavaativuus on O(2n), eli L 2 E.
2. (a) Olkoon syöteverkko G = (V; E), missä V = fv1; :::; vng, E = f(vi1; vj1); :::; (vim; vjm)g. Li- säksi syötteeseen kuuluvat alkusolmu u = vp ja loppusolmu v = vq, sekä polun maksimipi- tuus k. Koodataan syöte samaan tapaan kuin luentomuistiinpanojen sivulla 195 Hamiltonin kehä-ongelmalle. Syöte koodataan aakkoston f0; 1; g merkkijonona
^k ^p ^q ^i1 j^1 ^i2 j^2 : : : i^m j^m, missä ^i on luvun i binääriesitys.
(b) Ongelma voidaan ratkaista verkon leveyssuuntaisella läpikäynnillä (tietorakenteiden S04 luentomuistiinpanot, s. 201206). Sivulla 206 osoitetaan verkon läpikäymisen aikavaativuu- deksi O(jV j + jEj). Pahimmassa tapauksessa haku päätyy solmuun v vasta vierailtuaan kaikissa muissa solmuissa (näin käy esimerkiksi silloin, kun v:n etäisyys u:sta on suurempi kuin minkään muun solmun). Siten myös annetun ongelman vaativuus on O(jV j+jEj). Va- kio k ei vaikuta vaativuuden ylärajaan. Jos esimerkiksi k = 1, ja verkko on sellainen, että lähtösolmusta on suoraan kaari kaikkiin muihin solmuihin ("tähtimuoto"), voi silti käydä niin, että kaikissa muissa solmuissa vieraillaan ennen v:tä.
Tietorakenteiden muistiinpanoissa käytetään oleellisesti RAM-mallia, jossa ei huomioida solmujen ja kaarien koodaukseen kuluvien merkkien määrää. Syötteen pituudeksi tulkitaan siis jV j+jEj+3 = O jV j+jEj
. Käytettäessä Turingin koneita syötteen pituudella tarkoite- taan syötemerkkijonon pituutta, joka riippuu solmujen ja kaarien lukumäärän lisäksi kun- kin solmun ja kaaren koodaamiseen käytettävien merkkien määrästä. Yhden solmun esittä- minen vaatii O(log2(jV j)) merkkiä, ja kaaren esittäminen vastaavasti O(2 log2(jV j) + 1)=
O(log2(jV j)) merkkiä. Turingin koneelle syötteen pituus on siis O
log2(jV j) jV j + jEj . Luentomuistiinpanojen sivulla 175 todetaan, että jos kieli voidaan tunnistaa RAM-mallissa ajassa t(n), niin se voidaan tunnistaa Turingin koneella ajassa O(t(n)2). Annetun ongel- man ratkaisevan Turingin koneen aikavaativuus jV j:n ja jEj:n avulla ilmaistuna on siis O
log2(jV j)(jV j + jEj)2 .
3. Ongelmien kuuluminen luokkaan NP todistetaan laatimalla niille polynomisessa ajassa toimivat epädeterministiset ratkaisualgoritmit, jotka noudattavat seuraavaa edistynyttä periaatetta:
(a) Tarkistetaan, että syöte on oikeaa muotoa.
(b) Arvataan ratkaisu.
(c) Tarkistetaan, että arvaus oli oikea.
Riippumaton joukko -ongelman ratkaiseva algoritmi toimii seuraavasti:
Hylkää, jos syötteenä ei ole verkkoa (V; E) ja luonnollista lukua k.
Aseta U := ;.
Toista kaikilla v 2 V
Valitse epädeterministisesti U := U [ fvg tai U := U.
Jos jUj < k, hylkää syöte.
Toista kaikilla (u; v) 2 E
Jos u 2 U ja v 2 U, hylkää.
Hyväksy syöte.
Syötteen oikeellisuuden voi tarkistaa helposti polynomisessa ajassa sen kokoon nähden. Ratkai- suehdotuksen tuottavassa silmukassa suoritetaan (jV j) yksinkertaista operaatiota, joten myös sen aikavaativuus on polynominen. Ratkaisun tarkistavassa silmukassa taas suoritetaan (jEj) yksinkertaista operaatiota, joten sen ja siten koko algoritmin aikavaativuus jää polynomiseksi.
Algoritmi myös toimii oikein. Ensimmäinen silmukka voi tuottaa minkä tahansa osajoukon U V , joista välittömästi hylätään ne, joiden koko ei ole vähintään k. Deterministinen tar- kistussilmukka taas hylkää osajoukon U, jos jonkin kaaren (u; v) 2 E molemmat päät ovat joukossa U (jolloin se ei siis ole riippumaton joukko). Ainoastaan siinä tapauksessa, että arvattu osajoukko U on riittävän suuri riippumaton joukko, syöte hyväksytään. Näin käy välttämät- tä jollain arvauksella, jos syötteenä saadussa verkossa on vähintään kokoa k oleva riippumaton joukko.
Ositusongelman ratkaisualgoritmi on puolestaan seuraavanlainen:
2
Hylkää, jos syötteenä ei ole jonoa (a1; : : : ; an) luonnollisia lukuja.
Aseta A := ;, x := 0 ja y := 0.
Toista kaikilla i := 1 : : : n Aseta y := y + ai.
Valitse epädeterministisesti
Aseta A := A [ fig ja x := x + ai. tai Aseta A := A ja x := x.
Hyväksy, jos x = y=2.
Algoritmi toimii selvästi polynomisessa ajassa, sillä se sisältää vain syötteen oikeellisuuden tar- kistamisen, joitain alkeisoperaatioita sekä n kertaa suoritettavan alkeisoperaatioita sisältävän silmukan. Se käy läpi kaikki syötteenä saadun jonon alkiot ja valitsee epädeterministisesti, kuu- luuko kukin niistä joukkoon A vai ei. Samalla se laskee joukon A indeksoimien alkioiden summan x sekä kaikkien alkioiden summan y. Algoritmi hyväksyy syötteen, jos se onnistuu valitsemaan sellaisen osajoukon A, jolla pätee x = y=2. Koska algoritmi voi tuottaa minkä tahansa osajoukon A, se löytää myös tällaisen osajoukon, jos sellainen on olemassa. Toisaalta algoritmi ei hyväksy syötettä, ellei se löydä ehdot täyttävää osajoukkoa.
4. Olkoot kielet A 2 NP ja B 2 NP mielivaltaisia ja MAja MB vastaavasti jotkin niiden epädeter- ministiset tunnistajakoneet, jotka toimivat polynomisessa ajassa. Muodostetaan näiden konei- den avulla polynomisessa ajassa toimivat epädeterministiset tunnistajakoneet kielten yhdisteelle A [ B ja leikkaukselle A \ B. Tämä riittää osoittamaan, että A [ B 2 NP ja A \ B 2 NP . Yhdisteen tunnistava kone valitsee aluksi epädeterministisesti, toimiiko se kuten kone MA vai kuten kone MB. Koska kaikilla x 2 A [ B pätee x 2 A tai x 2 B, löytyy hyväksyviä laskenta- polkuja ainakin niissä tapauksissa, että alussa valitaan vastaavasti kone MA tai kone MB. Jos taa x 62 A [ B, ei mikään laskentapolku hyväksy syötettä, koska kumpikaan koneista MAja MB ei tee niin. Kone tunnistaa siis kielen A [ B, joten luokka NP on suljettu yhdisteen suhteen.
Leikkauksen tunnistava kone tallentaa ensin alkuperäisen syötteen kakkosnauhalle ja simuloi sit- ten koneen MAtoimintaa ykkösnauhalla. Jos MAhyväksyy, kone palauttaa ykkösnauhan alkuti- laan ja simuloi sillä sitten koneen MBtoimintaa. Jos tämäkin kone hyväksyy, syöte hyväksytään.
Koska kaikilla x 2 A \ B pätee x 2 A ja x 2 B, hyväksyvät sekä MA että MB syötteen, jolloin myös leikkauksen tunnistava kone hyväksyy sen. Jos taas x 62 A\B, ainakin toinen koneista hyl- kää sen, jolloin myös leikkauksen tunnistava kone hylkää sen. Kone tunnistaa siis kielen A \ B, joten luokka NP on suljettu myös leikkauksen suhteen.
Sitä puolestaan ei tiedetä, onko luokka NP suljettu komplementoinnin suhteen. Yleisesti kui- tenkin uskotaan, ettei näin ole. Jos olisi NP 6= co-NP , olisi tällöin P 6= NP 6= P SP ACE (mitä ei toistaiseksi tunneta), sillä luokat P ja P SP ACE ovat suljettuja komplementoinnin suhteen.
Toisaalta taas tunnetaan luokkaan NP kuuluvia ongelmia (kuten verkkojen isomorsuus: an- nettuna on verkot (V; E) ja (V0; E0) ja kysytään, onko olemassa bijektiota : V ! V0, jolla pätee (u; v) 2 E () ((u); (v)) 2 E0), joiden komplementin ei tiedetä kuuluvan luokkaan NP .
Suoraviivainen ajatus, jolla kielen A tunnistavasta koneesta MA saataisiin sen komplementin A tunnistava kone vaihtamalla hyväksyvä ja hylkäävä lopputila keskenään, ei toimi. Kone MA nimittäin hyväksyy syötteen, jos sillä on ainakin yksi hyväksyvä laskentapolku, ja hylkää sen muussa tapauksessa. Epädeterministinen kone MA0, jossa hyväksyvä ja hylkäävä lopputila on vaihdettu keskenään, hyväksyisi kyllä kaikki merkkijonot x 62 A. Se hyväksyisi kuitenkin myös ne merkkijonot x 2 A, joilla on koneella MAmyös hylkääviä laskentapolkuja. Näin ollen lopputilojen vaihtaminen tuottaa komplementin tunnistavan koneen vain siinä tapauksessa, että kaikilla x 2 A koneen MA kaikki laskentapolut ovat hyväksyviä.
3
