next up previous
Next: About this document Up: No Title Previous: No Title

Algoritmiteorian jatkokurssi, kevät 1999
Harjoitus 1: ratkaisuja (KP teht. 2-6, PO täydenn. & teht. 1)

  1. Äärelliset automaatit ovat oleellisesti Turingin koneita ilman työnauhaa. Tarkemmin sanoen: annettu äärellinen automaatti voidaan helposti muuttaa Turingin koneeksi, joka käyttää työnauhaltaan vain aloituspaikan (jos nauhapään on konemallissa mahdollista pysyä siirtymän yhteydessä paikallaan), tai aloituspaikan ja sen viereisen paikan (jos nauhapäätä on pakko siirtää, sitä voidaan siirrellä edestakaisin näiden kahden paikan välillä). Jos säännöllisten kielten luokkaa merkitään REG, on siis tex2html_wrap_inline696 tai tex2html_wrap_inline698 valitun Turingin kone -mallin yksityiskohtien mukaan.

    Äärellisestä automaatista muokattu Turingin kone tekee n merkin mittaisella syötteellä n+1 siirtymää ennen pysähtymistään ((n+1):s siirtymä tarvitaan loppumerkin havaitsemiseen). Aikavaativuuden suhteen on siis voimassa tex2html_wrap_inline706 .

    Lisätietoja: Itse asiassa voidaan osoittaa, että tex2html_wrap_inline708 kaikilla vakioilla tex2html_wrap_inline710 : äärellinen automaatti voi pitää sisäisessä tilassaan kirjaa simuloimansa Turingin koneen työnauhan sisällöstä, jos nauha on rajoitetun pituinen, ja lisäksi tiedetään että mahdollisuus siirtää syötenauhapäätä myös vasemmalle ei lisää äärellisten automaattien kielentunnistusvoimaa. Mielenkiintoisempi tulos on, että tex2html_wrap_inline712 peräti kaikilla tex2html_wrap_inline714 . (Luentomuistiinpanojen Lause 1.8.)

    Sen sijaan luokka tex2html_wrap_inline716 (ns. ``reaaliaikakielet'') sisältää muitakin kuin säännöllisiä kieliä: esimerkiksi palindromikieli tex2html_wrap_inline718 on helppo tunnistaa ajassa n+1, mutta on tunnetusti ei-säännöllinen.

  2. Oletetaan, että luettelo tex2html_wrap_inline722 sisältää kaikki moninauhaiset Turingin koneet.gif

    Määritellään Turingin koneen M toiminta syötteellä c seuraavasti:

    - M laskee funktion arvon t(|c|) ja asettaa aikarajoituslaskurille arvon t(|c|) + 1.

    - M simuloi koneen tex2html_wrap_inline738 toimintaa syötteellä c vähentäen jokaisella laskenta-askelella aikarajoituslaskuria yhdellä. Jos tex2html_wrap_inline738 pysähtyy hyväksyvässä lopputilassa, M hylkää c:n. Jos tex2html_wrap_inline738 pysähtyy hylkäävässä lopputilassa tai aikalaskuri nollautuu, M hyväksyy c:n.

    Näin määritelty Turingin kone M tunnistaa kielen tex2html_wrap_inline756 . Koska M pysähtyy kaikilla syötteillä, se on totaalinen. Näin ollen tex2html_wrap_inline756 on rekursiivinen kieli.

    Oletetaan, että tex2html_wrap_inline762 . Silloin on olemassa kielen tex2html_wrap_inline756 ajassa t tunnistava Turingin kone N, joka on sama kuin tex2html_wrap_inline770 jollakin tex2html_wrap_inline772 .

    Jos tex2html_wrap_inline774 , niin N hyväksyy syötteen d ajassa t(|d|) ja silloin tex2html_wrap_inline756 :n määritelmän mukaan tex2html_wrap_inline784 . Jos tex2html_wrap_inline784 , niin N hylkää syötteen d ja silloin tex2html_wrap_inline756 :n määritelmän mukaan tex2html_wrap_inline774 . Ristiriita johtuu oletuksesta, että tex2html_wrap_inline796 DTIME(t). Siis tex2html_wrap_inline800 DTIME(t).

    [Lisätieto (PO): Jos funktio t(n) on aikakonstruoituva, niin kone M saadaan toimimaan ajassa t'(n) millä tahansa tex2html_wrap_inline810 . Tällaisilla funktiopareilla on siis aina tex2html_wrap_inline812 . Lisätekijän tex2html_wrap_inline814 aiheuttaa se, että koneen M täytyy simuloida koneen tex2html_wrap_inline738 mielivaltainen nauhamäärä kiinteällä nauhajoukolla, ja tex2html_wrap_inline820 -luokituksen se, että tämän lisäksi tarvitsee vielä koneen tex2html_wrap_inline738 mielivaltainen nauha-aakkosto koodata M:n kiinteälle aakkostolle.]

  3. Väite. Olkoon tex2html_wrap_inline826 polynomisessa ajassa laskettava ja tex2html_wrap_inline828 . Tällöin tex2html_wrap_inline830 P.

    Todistus. Kieleen tex2html_wrap_inline832 kuuluvat ne tex2html_wrap_inline834 :n merkkijonot y, joilla f(y) = x.

    Olkoon M Turingin kone, joka laskee funktion f polynomisessa ajassa t. Määritellään Turingin kone tex2html_wrap_inline846 siten, että se laskee syötteellä y M:n tavoin funktion arvon f(y) ja vertaa sitä x:ään pysähtyen hyväksyvässä lopputilassa, jos f(y) = x, ja hylkäävässä lopputilassa, jos tex2html_wrap_inline858 . Tämä tex2html_wrap_inline846 tunnistaa kielen tex2html_wrap_inline832 . On vielä osoitettava, että tex2html_wrap_inline846 :n laskenta tapahtuu polynomisessa ajassa.

    Syötteellä y tex2html_wrap_inline846 laskee f(y):n polynomisessa ajassa ja, koska tex2html_wrap_inline872 , myös f(y):n vertailu x:ään tapahtuu polynomisessa ajassa. Siten tex2html_wrap_inline878 . -.5ex tex2html_wrap_inline880

    Olkoon tex2html_wrap_inline882 ja tex2html_wrap_inline884 P. Laskekoon Turingin kone tex2html_wrap_inline886 syötteellä y M:n tavoin funktion arvon f(y) ja testatkoon sen kuulumisen kieleen A. Laskenta tapahtuu polynomisessa ajassa, joten tex2html_wrap_inline896 P.

  4.   Väite. Olkoot A, tex2html_wrap_inline900 ja A, tex2html_wrap_inline904 P. Tällöin
    1. tex2html_wrap_inline906 P,
    2. tex2html_wrap_inline908 P ja
    3. tex2html_wrap_inline910 P.
    Todistus. Olkoot M ja N Turingin koneita, jotka tunnistavat kielet A ja B polynomisessa ajassa.
    1. Turingin koneesta M saadaan vaihtamalla keskenään sen hyväksyvät ja hylkäävät lopputilat kielen tex2html_wrap_inline922 polynomisessa ajassa tunnistava Turingin kone. Siten tex2html_wrap_inline906 P.
    2. Määritellään Turingin koneen H toiminta syötteellä x seuraavasti:

      - H testaa syötteen kuulumisen kieleen A kuten M. Myönteisessä tapauksessa H pysähtyy hyväksyvässä lopputilassa.

      - Muuten H testaa syötteen kuulumisen kieleen B kuten N. Myönteisessä tapauksessa H pysähtyy hyväksyvässä, kielteisessä hylkäävässä lopputilassa.

      Näin määritelty Turingin kone H tunnistaa kielen tex2html_wrap_inline948 . Tunnistus tapahtuu polynomisessa ajassa, sillä kumpikin kieli erikseen tunnistetaan polynomisessa ajassa. Siten tex2html_wrap_inline908 P.

    3. Väite seuraa edellisistä kohdista, sillä

      displaymath694

  5. Olkoot A, tex2html_wrap_inline900 ja A, tex2html_wrap_inline904 NP. Tällöin
    1. tex2html_wrap_inline908 NP ja
    2. tex2html_wrap_inline910 NP.
    Todistus. Olkoot M ja N epädeterministisiä Turingin koneita, jotka tunnistavat kielet A ja B epädeterministisesti polynomisessa ajassa.
    1. Määritellään epädeterministisen Turingin koneen H toiminta syötteellä x seuraavasti:

      - H testaa syötteen kuulumisen kieleen A kuten M. Myönteisessä tapauksessa H pysähtyy hyväksyvässä lopputilassa.

      - Muuten H testaa syötteen kuulumisen kieleen B kuten N. Myönteisessä tapauksessa H pysähtyy hyväksyvässä, kielteisessä hylkäävässä lopputilassa.

      Näin määritelty epädeterministinen Turingin kone H tunnistaa kielen tex2html_wrap_inline948 epädeterministisesti. Tunnistus tapahtuu polynomisessa ajassa, sillä kumpikin kieli erikseen tunnistetaan polynomisessa ajassa. Siten tex2html_wrap_inline908 NP.

    2. Määritellään epädeterministisen Turingin koneen K toiminta syötteellä x seuraavasti:

      - K testaa syötteen kuulumisen kieleen A kuten M. Kielteisessä tapauksessa K pysähtyy hylkäävässä lopputilassa.

      - Muuten K testaa syötteen kuulumisen kieleen B kuten N. Myönteisessä tapauksessa K pysähtyy hyväksyvässä, kielteisessä hylkäävässä lopputilassa.

      Näin määritelty epädeterministinen Turingin kone K tunnistaa kielen tex2html_wrap_inline1022 epädeterministisesti. Tunnistus tapahtuu polynomisessa ajassa, sillä kumpikin kieli erikseen tunnistetaan polynomisessa ajassa. Siten tex2html_wrap_inline910 NP. -.5ex tex2html_wrap_inline880

    Jos NP:n sulkeisuutta komplementoinnin suhteen yritetään todistaa samalla metodilla kuin tehtävässä 4, ongelmana on kielen A tunnistavan Turingin koneen M epädeterministisyys. Epädeterministinen Turingin kone hyväksyy syötteen, jos koneen laskenta päätyy jollakin laskentapolulla koneen pysähtymiseen hyväksyvässä lopputilassa. Ei ole kielletty, että samalla syötteellä voitaisiin päätyä toisella laskentapolulla koneen pysähtymiseen hylkäävässä lopputilassa. Koneen lopputila ei siis yksikäsitteisesti liity syötteen hyväksymiseen kuten deterministisellä Turingin koneella.
  6. Lemma. co-P = P ja co-PSPACE = PSPACE.

    Todistus. Ensimmäinen väite seuraa tehtävästä 4. Jälkimmäinen todistetaan seuraavasti:

    Jos tex2html_wrap_inline884 PSPACE, niin kielen A polynomisessa tilassa tunnistavasta Turingin koneesta saadaan vaihtamalla keskenään sen hyväksyvät ja hylkäävät lopputilat kielen tex2html_wrap_inline922 polynomisessa tilassa tunnistava Turingin kone. Siten tex2html_wrap_inline906 PSPACE. -.5ex tex2html_wrap_inline880

    1. Triviaalisti tex2html_wrap_inline1042 .

      Jos tex2html_wrap_inline884 P, niin tex2html_wrap_inline906 P tex2html_wrap_inline1048 NP, joten tex2html_wrap_inline884 co-NP. Näin ollen P tex2html_wrap_inline1048 NP tex2html_wrap_inline1054 co-NP.

    2. Kun tex2html_wrap_inline1056 , lauseen 7.5gif mukaan DTIME tex2html_wrap_inline1058 DSPACE(t). Samalla tavalla samalla ehdolla voidaan päätellä, että NTIME tex2html_wrap_inline1058 NSPACE(t). Niinpä NP tex2html_wrap_inline1048 NPSPACE = PSPACE (lauseen 7.10 mukaan).

      Jos tex2html_wrap_inline884 co-NP, niin tex2html_wrap_inline906 NP tex2html_wrap_inline1048 PSPACE, joten A tex2html_wrap_inline1074 co-PSPACE = PSPACE. Näin ollen NP tex2html_wrap_inline1076 co-NP tex2html_wrap_inline1048 PSPACE.

    3. Jos P = NP, niin co-NP = co-P = P = NP. Jos NP = PSPACE, niin co-NP = co-PSPACE = PSPACE = NP. Näilllä päättelyillä väitteet todistuvat epäsuorasti.

next up previous
Next: About this document Up: No Title Previous: No Title

Pekka Orponen
Mon Apr 12 19:37:09 EET DST 1999