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