Aika ja Tila.

Turing-vahvoissa laskennan malleissa on se hyvä puoli, että ne voidaan redusoida toisikseen melko robustilla tavalla, so. niin, että useimmat tärkeimmät kompleksisuusluokat säilyvät. Esimerkiksi reduktio yksinauhaisen Turingin koneen ja RAM-koneen välillä on polynomisen ajan suhteen täysin robusti. Vaikka RAM-kone voi lukea vakioajassa minkä tahansa kirjoittamansa muistipaikan siinä, missä Turingin kone joutuu käyttämään lineaarisen ajan tämän paikan etsimiseen, tämä kerroin ei kuitenkaan ole koskaan eksponentiaalinen, koska jos RAM-kone on kirjoittanut polynomiseen määrään muistipaikkoja, niiden kaikkien kelaaminen Turingin nauhalta kuluttaa vain polynomisen ajan.

Aikaluokista tutuin varmaankin on juuri P, polynomiaikaisten päätöstehtävien joukko. Tämä tarkoittaa niitä ongelmia, joihin voidaan "kyllä"- ja "ei"- vastaukset löytää ajassa, jota rajaa yläpuolelta jokin polynomi ongelman kuvauksen pituudesta. Esimerkiksi "onko annettu lukujono suuruusjärjestyksessä" on polynomiaikainen. Hieman monimutkaisempi voisi olla esimerkiksi kysymys, onko annettujen järjestämättömien lukuparien joukossa neljän "klikkiä". (Klikki on joukko, jonka kaikki mahdolliset yhdistelmät ovat mukana, esimerkiksi {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)} olisi tällainen) Sekin on luokassa P, koska neljän alkion osajoukkoja voi annetulle joukolle olla vain määrä, joka on verrannollinen ko. joukon alkioiden määrän neljänteen potenssiin, joten ne voidaan kaikki tarkastaa. Sensijaan tämän yleistys, onko annetussa n:n luvun parien joukossa n/3:n alkion klikkiä, ei ole (välttämättä) P:ssä, koska n/3:n alkion joukkoja on eksponentiaalinen määrä.

PSPACE puolestaan on sellaisten päätöstehtävien joukko, joiden ratkaisemiseksi tarvitaan polynominen määrä muistia (tai nauhaa tms). On selvää, että P on joukon PSPACE osajoukko, mutta näistä ei tiedetä, ovatko ne eri joukot. Useimmat uskovat, että kyllä ovat.

Tilan suhteen voidaan mennä vielä pienempään sumppuun, ns. logaritmiseen tilaan. Näiden joukko, L, sisältää sellaiset päätöstehtävät, joiden ratkaisemiseksi tarvittava muisti on korkeintaan logaritminen, kun itse syöte on jätetty pois laskuista. Tällaisia ongelmia ei äkkiä ajatellen olisi paljoa, mutta esimerkiksi yhteenlaskun oikeellisuuden tarkastaminen on tällainen: Jos meille on annettu kolme binäärilukuna annettua kokonaislukua, a, b,c, ja haluamme tarkastaa, josko a+b = c, niin tarvitsemme itseasiassa vain vakiomäärän ylimääräistä muistia, eli ns. carry-luvun (maks. kaksi merkitsevää numeroa). Oletetaan, että a(i) on a:n i:nneksi vähiten merkitsevä numero (vast. luvuille b ja c). Asetamme x:ksi 0:n ja laskemme vähiten merkitsevästä numerosta alkaen a(i) + b(i) + x, ja tästä voidaan tarkastaa, että sen alin numero on c(i), ja asetetaan x:n uudeksi arvoksi tämän luvun ylempi numero (joka on itseasiassa aina 1 tai 0). Indeksi "i" on ainoa asia, joka tässä kuluttaa muuta kuin vakiomäärän muistia, mutta suurimmillaankin sen vaatiman esityksen koko on syötteen koon logaritmiin verrannollinen.

Tällä kertaa muuten valitsin musiikkikappaleen siksi, että kuulin sen aamulla radiosta, ja se toi mieleeni 90-luvun.