Vapaa ultrafiltteri

Kevään viimeistein opiskelukiireiden vähitellen helpottaessa sain lopultakin tehtyä erään asian, joka on ollut jo vähän aikaa tarkoituksena saada aikaiseksi. Hankin nimittäin itselleni graduohjaajan ja -aiheen. Niille joille sana “gradu” on entuudestaan tuntematon, kerrottakoon, että pro gradu -tutkielma on maisterin tutkinnon lopputyö, jossa opiskelijan tulee osoittaa kykenevyytensä tieteelliseen ilmaisuun. Toisin sanoen siis pitkä ja kattava kirjoitustehtävä, jonka sisällön pitää olla asiaa. Toistaiseksi prosessi on vielä alkuvaiheessa ja tarkka aiheenrajaus on vielä tekemättä, mutta onpahan tämäkin alku.

Graduni tulee näillä näkymin käsittelemään deskriptiivistä kompleksisuusteoriaa, joka on vahvasti teoreettiseen tietojenkäsittelytieteeseen liittyvä osa äärellistä malliteoriaa. Vielä yleisemmällä tasolla kyseinen ala putoaa logiikan alle. Aiheen abstraktiuden vuoksi sen yksityiskohtainen purkaminen tässä blogissa jäänee väliin, mutta sen yhteydet tietojenkäsittelytieteeseen antavat konkreettisemman tavan lähestyä sen keskeisiä ajatuksia.

Teoreettisessa tietojenkäsittelytieteessä yksi tärkeistä kysymyksistä on se, kuinka nopeasti jokin annettu ongelma voidaan ratkaista tietokoneella. Koska tietokoneissa on nykyään niin valtavasti eroja ja prosessorit ovat huomattavan monimutkaisia, kysymystä tarkastellaan yleensä abstraktimmasta viitekehyksestä ja unohdetaan oikea tietokoneet. Tietojenkäsittelytieteen puolella tämä tehdään yleensä tarkastelemalla matemaattista “ideaalista” tietokonetta, Turingin konetta, ja kiinnostuksen kohteena on erityisesti kuinka laskentaan vaaditun ajan määrä kasvaa syötteen kasvaessa. Tarkemmin ottaen halutaan määrittää jokin funktio, joka vakiokertoimia lukuunottamatta toimii ylärajana ongelman ratkaisevan ohjelman vaatimille laskenta-askelille, kun parametrina annetaan syötteen koko. Esimerkiksi jos on annettuna n kappaletta lukuja, ne voidaan järjestää ajassa n^2, eli laskenta-askelia tarvitaan aina vähemmän kuin joku vakiokerroin kertaa n^2. Tämä tulos saadaan suhteellisen helposti esittämällä jokin sopiva algoritmi lukujen järjestämiseen. Vastaavasti tietysti voidaan tarkastella laskentaongelman vaatiman muistin määrää.

Teoreettisesta näkökulmasta asioita voidaan abstrahoida vielä lisää ja määritellä laskentaongelmien luokkia, jotka ovat tietyllä tapaa luonnollisia. Esimerkiksi PTIME on niiden laskentaongelmien luokka, joiden aikavaativuus on funktiota n^d pienempi jollain luonnollisella luvulla d. PSPACE on vastaava luokka, kun rajoitteena pidetään ohjelman käyttämää muistin määrää ajan sijasta. Tavallaan voidaan ajatella, että PTIME on inhimillisessä ajassa laskettavien ongelmien luokka ja vastaavasti PSPACE sisältää ne ongelmat, jotka voidaan ratkaista käyttämällä järjellinen määrä muistia. Eräs toinen merkittävä luokka on NPTIME. Se poikkeaa edellisistä luokista siinä mielessä, ettei sen määritelmässä tarkastella suoraan ongelmien vaatimaa aikaa, vaan vaaditaan, että jos meille on etukäteen annettu vastaus ongelmaan, niin meidän täytyy pystyä tarkastamaan vastauksen oikeellisuus nopeasti. Toisin sanoen NPTIME-ongelman oikean vastauksen varmistaminen oikeaksi on PTIME-ongelma. Toinen määritelmä NPTIME:lle saataisiin epädeterminististen – siis tietyssä mielessä rinnakkaislaskevien – Turingin koneiden kautta, mutten käsittele aihetta tässä.

Näihin vaativuusluokkiin liittyy paljon hyvinkin merkittäviä avoimia kysymyksiä. Tiedetään esimerkiksi, että kaikki PTIME-ongelmat ovat myös NPTIME-ongelmia ja vastaavasti kaikki NPTIME-ongelmat PSPACE-ongelmia, eli PTIME on mainituista luokista “helpoin” ja PSPACE “vaikein”. Toisaalta ei ole mitään takeita siitä, että luokat PTIME ja NPTIME olisivat erilliset – on siis mahdollista että tapa tarkastaa ratkaisu nopeasti antaa suoraan nopean tavan löytää vastaus. Suurin osa tietojenkäsittelytieteilijöistä kuitenkin uskoo, johtuen vahvoista viitteistä tähän suuntaan, että PTIME ja NPTIME eivät ole sama luokka. Kaikki modernit salausmenetelmät perustuvatkin tälle olettamukselle ja itse asiassa tämä P-NP-ongelma on yksi merkittävimmistä matematiikan avoimista kysymyksistä.

Tämän kaiken pohjustuksen jälkeen päästään sitten deskriptiiviseen kompleksisuusteoriaan. Siinä ajatuksena on, että tietokoneohjelmien syötteitä voidaan pitää matemaattisina malleina, ja niistä voidaan puhua logiikan avulla. Huomautettakoon toki, että tässä logiikka tulkitaan hyvin yleisessä muodossa, eli logiikka on periaatteessa mikä tahansa formaali kieli, jolla on hyvin määritelty merkitys ja jota voidaan käyttää malleista puhumiseen. Näin havaitaan, että vaativuusluokille voidaan löytää logiikat, joiden ilmaisuvoima on vastaa vaativuusluokassa laskettavia asioita. Siis esimerkiksi luokkaa PTIME vastaa logiikka FO(IFP), niin että logiikassa FO(IFP) voidaan kuvailla täsmälleen ne mallien ominaisuudet, joiden kohdalla on PTIME-ongelma selvittää onko annetussa tietokoneen syötteessä kyseinen ominaisuus. Tavallaan nämä logiikat voidaan siis nähdä “ohjelmointikielinä”, joilla voi ratkaista vain tietyn luokan ongelmia. Tällaisten logiikoiden olemassaolo sekä tarjoaa uusia työkaluja luokkien suhteiden tutkimiseen sekä antaa jossain mielessä kauniimpia karakterisaatioita vaativuusluokille. Huomautettakoon vielä kuitenkin, että deskriptiivisessä kompleksisuusteoriassakin on vielä paljon keskeisiä kysymyksiä, joihin ei tunneta vastausta.

Tämänkertainen aihe oli tosiaan vielä abstraktimpi kuin aikaisemmat matematiikka-merkintäni. Jos koet, että joku kohta oli epäselvä, kaipaat muuten vaan selvennystä tai mieleesi tulee miten asian voisi ilmaista fiksummin, jätä ihmeessä kommentti.