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 tai 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 .

   Lisätietoja: Itse asiassa voidaan osoittaa, että kaikilla vakioilla : ää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ä peräti kaikilla . (Luentomuistiinpanojen Lause 1.8.)

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

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

   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 toimintaa syötteellä c vähentäen jokaisella laskenta-askelella aikarajoituslaskuria yhdellä. Jos pysähtyy hyväksyvässä lopputilassa, M hylkää c:n. Jos pysähtyy hylkäävässä lopputilassa tai aikalaskuri nollautuu, M hyväksyy c:n.

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

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

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

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

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

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

   Olkoon M Turingin kone, joka laskee funktion f polynomisessa ajassa t. Määritellään Turingin kone 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 . Tämä tunnistaa kielen . On vielä osoitettava, että :n laskenta tapahtuu polynomisessa ajassa.

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

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

4.   Väite. Olkoot A, ja A, P. Tällöin
   1. P,
   2. P ja
   3. 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 polynomisessa ajassa tunnistava Turingin kone. Siten 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 . Tunnistus tapahtuu polynomisessa ajassa, sillä kumpikin kieli erikseen tunnistetaan polynomisessa ajassa. Siten P.

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

      

5. Olkoot A, ja A, NP. Tällöin
   1. NP ja
   2. 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 epädeterministisesti. Tunnistus tapahtuu polynomisessa ajassa, sillä kumpikin kieli erikseen tunnistetaan polynomisessa ajassa. Siten 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 epädeterministisesti. Tunnistus tapahtuu polynomisessa ajassa, sillä kumpikin kieli erikseen tunnistetaan polynomisessa ajassa. Siten NP. -.5ex

   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 PSPACE, niin kielen A polynomisessa tilassa tunnistavasta Turingin koneesta saadaan vaihtamalla keskenään sen hyväksyvät ja hylkäävät lopputilat kielen polynomisessa tilassa tunnistava Turingin kone. Siten PSPACE. -.5ex

   1. Triviaalisti .

      Jos P, niin P NP, joten co-NP. Näin ollen P NP co-NP.

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

      Jos co-NP, niin NP PSPACE, joten A co-PSPACE = PSPACE. Näin ollen NP co-NP 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.