Deskriptiivinen kompleksisuus

Kompleksisuusteoria on tietojenkäsittelytieteen osa-alue, joka käsittelee sitä, miten tehokkaasti tietynlaiset ongelmat voidaan ratkaista, kun käytössä on jokin tietty formalismi jolla laskentaa tms suoritetaan. Esimerkiksi, meillä on taulukko (tai muu vastaava tietorakenne) A, jossa on lukuja.  Emme nyt problematisoi lukujen esittämisen vaatimia resursseja (suuren luvun esittäminen vaatii paljon bittejä), vaan abstrahoimme tässä nyt sen osan pois. Oletetaan, että taulukon koko on n, ja me pääsemme käsiksi taulukon i:nteen alkioon vakioajassa. Viittaamme tähän alkioon A[i].  Oletamme että kaikki taulukon alkiot ovat erisuuria. (Tämä oletus ei ole olennainen tai välttämätön, mutta teen sen typografisista syistä...)

Tehtävämme on siirrellä taulukon alkioita siten, että siirtelyn jälkeen taulukko on järjestyksessä. Tämä tarkoittaa sitä, että jokaisella kokonaisluvulla i välillä 1 < i < n+1 pätee että A[i-1] < A[i]. Tämä ei siis päde alussa. Meillä on käytössämme kaksi operaatiota, V(i,j), joka vaihtaa taulukon alkiot i ja j keskenään, sekä vertailuoperaatio A[i] < A[j].

Emme nyt keskustele siitä, miten tarkalleenottaen toteutamme taulukon järjestämisen. Oletamme että taulukko on alussa täysin sekaisin, emmekä tiedä mitään esimerkiksi siitä, mitä arvoja taulukossa on ja miten ne ovat jakautuneet. Voimme ilmaista taulukon järjestämisen permutaation etsimisenä, ja tarkastelemme ongelman kompleksisuutta tästä näkökulmasta.

Koska alkiot ovat erisuuria, on keskenään erilaisia tapoja laittaa alkiot taulukkoon n! kappaletta, missä n! = 1*2*...*n. Tämä tulee siitä, että ensimmäinen alkio voi olla mikä hyvänsä n:stä alkiosta, tämän jälkeen toinen voi olla mikä hyvänsä jäljellä olevista, jne. Näistä n!-kappaleesta permutaatioita meidän tulee löytää se, joka vastaa taulkon järjestyksessä olemista.

Jokainen vertailu, jonka taulukolle teemme, paljastaa meille jotain siitä, minkälaisen permutaation tarvitsemme. Tarkalleenottaen, kaikkien vielä mahdollisten permutaatioiden joukosta yksi vertailu sulkee pois tarkalleen puolet. Nimittäin, vertaamalla A[i] < A[j], (missä i < j) tulos on "kyllä" tasan silloin kun nämä alkiot ovat oikeassa järjestyksesä ja "ei" silloin kun oikeassa permutaatiossa ne ovat eri järjestyksessä. Muuta informaatiota emme yksittäisestä vertailusta (yleisessä tapauksessa) saa. Yhden vertailun (ja mahdollisen vaihdon) jälkeen permutaatiota on jäljellä n!/2, ja jokainen vertailu vastaavasti puolittaa permutaatioiden määrän. Tätä puolittamista on pahimmassa tapauksessa jatkettava kunnes permutaatioita on enää yksi. Tiedämme, että tällöin olemme tehneet log(n!) puolitusta. log(n!) on suunnilleen n*log(n), mikä tarkoittaa, että pahimmassa tapauksessa taulukon järjestämiseksi täytyy tehdä (osapuilleen) tämän verran vertailuja ja vaihtoja.

Tämä on yksinkertaisimpia analyysejä joilla voidaan tarkastella miten kompleksinen jokin ongelma on; tämä paljasti siis, että taulukon järjestäminen ei onnistu (aivan) suoraan taulukon kokoon verrannollisessa ajassa.

Vaikeampien kysymysten analysoiminen on usein -- niin -- vaikeampaa.  Deskriptiivinen kompleksisuusteoria on teoria, joka yksittäisten ongelmien kompleksisuuden sijaan pyrkii luokittelemaan ongelmia sen mukaan, millä tavoin ne ovat ilmaistavissa. Oletetaan, että meillä on syötteenä jokin struktuuri ja jollakin logiikalla ilmaistu ominaisuus, ja tehtävänä on selvittää, onko annetulla struktuurilla tämä ominaisuus. Ongelman vaikeus riippuu siitä, millaisia ilmaisutapoja logiikassa on käytössä.

Esimerkiksi, jos meillä on annettu syötteenä graafi (eli suomeksi "verkko", mutta käytän tätä termiä välttääkseni sekaannusta) ja jokin ensimmäisen kertaluvun predikaattilogiikan kaava ja annettu joukko predikaatteja, voimme itseasiassa hyvinkin helposti tarkastaa onko kaava tosi. Tässä siis oletamme, että nämä predikaatit todella on annettu, eli pystymme suoraan laskemaan niiden arvon mille tahansa alkioille. Esimerkiksi "Kaikille solmuille x,y, pätee että niiden välillä on kaari" Tai "on olemassa solmut x, y, z siten, että (x,y) on kaari ja (y,z) on kaari".

Tätä ei pidä sekoittaa siis sellaiseen tilanteeseen jossa on annettu kaava, ja pitää selvittää päteekö kyseinen kaava ylipäätään jollekin mallille, eikä myöskään tilanteeseen, jossa predikaattien arvoja ei tunneta, ja pitäisi tietää voidaanko predikaateille antaa sellainen tulkinta, jolla kaava pätee annetulle struktuurille.

Ongelmat, jotka on ilmaistavissa tällä tavalla, ovat luokassa FO (sanoista First Order), ja deskriptiivisen kompleksisuusteorian yksi tulos on, että tämä luokka on sama kuin AC0, joka puolestaan tarkoittaa ongelmia jotka voidaan ratkaista hyvin tehokkaasti; Jokaiselle tällaiselle ominaisuudelle on olemassa hierarkia ongelman ratkaisevia logiikkapiirejä, joiden syvyys (perättäisten porttien määrä) on rajoitettu.  On huomattava, että tämän luokan yksittäisen ongelman karakterisoi nimenomaan yksittäinen predikaattilogiikan kaava (joka kullekin ongelmalle on kiinteä), ja mahdollisten struktuurien joukko.

FO ongelmat eivät ole esimerkiksi graafeille kovin mielenkiintoisia, koska vaikkapa kysymystä "Onko kahden annetun solmun välillä polku" ei voidan ilmaista ensimmäisen kertaluvun predikaattilogiikalla.

Jos haluamme nimittäin karakterisoida jälkimmäisen tapauksen, niin tarvitsemme toisen kertaluvun logiikkaa. Täysi toisen kertaluvun logiikka antaa meille mahdollisuuden ilmaista esimerkiksi sen, että "on olemassa predikaatti P(x,y) siten, että...". Aivan vielä emme kuitenkaan ota näin vahvaa ilmaisuvoimaa mukaan.

Transitiivinen sulkeuma on operaatio, jonka lisääminen FO:iin tuo sopivasti ilmaisuvoimaa. Esimerkiksi, jos syötteenä on suunnattu graafi, niin meillä on automaattisesti käytössämme predikaatti p(x,y), joka sanoo että solmusta x on solmuun y vievä kaari. Lisäämme logiikkaamme operaattorin TC, joka toimii siten, että jos Q(x,y) on osakaava jossa on kaksi vapaata muuttujaa, niin TC(Q)(x,y) määrittelee tämän osakaavan Transitiivisen sulkeuman. Sen totuusarvo käyttäytyy seuraavalla tavalla: TC(Q(x,y)) tulkitaan itseasiassa siten, että joko Q(x,y) pätee, tai pitää löytyä jokin ei-tyhjä jono alkioita z1, z2, ..., zk siten, että Q(x,z1) pätee, Q(z1,z2) pätee, jne, ja Q(zk, y) pätee.

FO[TC] on niiden ongelmien joukko, jotka voidaan ilmaista käyttäen ensimmäisen kertaluvun logiikkaa ja transitiivista sulkeumaa. Esimerkiksi "Graafissa on polku solmusta s solmuun t" on ilmaistavissa tällä; jos p(x,y) on (annettu) predikaatti, joka pätee kun on kaari solmusta x solmuun y, niin polku solmusta s solmuun t on olemassa, jos pätee TC(p)(s,t). Tämä kompleksisuusluokka on sama kuin luokka NL, joka on niiden ongelmien luokka, jotka voidaan ratkaista "arvaamalla" ratkaisu askel kerrallaan ilman että koko ratkaisua täytyy muistaa.

Least fixpoint, eli pienimmän kiintopisteen operaattori taas mahdollistaa yksinkertaisen rekursiivisen ilmaisun, jolla määritellään uusi predikaatti. Muistutan tässä kohtaa, että olemassaolevat predikaatit ovat kiinteitä ja tunnettuja; TC yllä mahdollisti "uuden" predikaatin luomisen vanhojen predikaattien avulla hyvin yksinkertaisesti. LFP-operaattori on jo selvästi monimutkaisempi. Luodaksemme "toisen kertaluvun" predikaatin P -- eli predikaatin jonka tulkinta ei ole kiinnitetty -- ilmaisemme sen muodossa LFP(Q(P,x)) Tässä siis LFP-operaattorin sisään tulee kaava Q, jossa käytetään predikaattia P, muuttujia x ja olemassaolevia predikaatteja. Tämä tulkitaan tarkoittavan "pienintä" sellaista predikaattia P, joka toteuttaa kaavan P(x) = Q(P(x),x) kaikilla x; Rajoituksena on, että P(x) ei saa esiintyä negatiivisena kaavassa Q (so. kun kaava Q kirjoitetaan konjunktiiviseen normaalimuotoon, P:n negaatio ei saa esiintyä kaavassa). 

Esimerkiksi relaation p(x,y) transitiivinen sulkeuma voidaan ilmaista LFP-operaattorilla kaavasta  LFP(p(x,y) || \exists z: P(x,z) && p(z,y)). Eli, P(x,y) on p:n transitiivinen sulkeuma, kun se on "pienin" relaatio joka toteuttaa em rekursiivisen määritelmän. Pienin tässä yhteydessä tarkoittaa, että se joukko pareja, joka yhtälön toteuttaa, on minimaalinen; mikään sen aito osajoukko ei voisi toteuttaa yhtälöä.  FO[LFP] = P, eli polynomisessa ajassa ratkeavat ongelmat ovat karakterisoitavissa LFP-operaattorilla rikastetussa ensimmäisen kertaluvun predikaattilogiikassa. Tämä teoreema on hankalahko todistaa, joten en tässä ala sitä nyt käymään läpi.

Jos siirrymme toisen kertaluvun logiikkaan "aidosti", eli sallimme uusien predikaattimuuttujien esittelyn, mutta rajoitumme eksistentiaaliseen kvantifiointiin, saamme mielenkiintoisen luokan, SO[E]. Tässä siis on kyse ensimmäisen kertaluvun logiikasta, jossa saa luoda predikaattimuuttujia, kunhan ne on sidottu olemassaolokvanttorilla. Käytän tässä merkintää \E, koska en jaksa kaivaa symboleja.

Tällöin voidaan sanoa vaikkapa että \E(P(x,y): P(x,y) <=> (p(x,y) || (\Ez: P(x,z) && p(z,y) && \Ez: p(x,z) && O(z,y)). Tämä siis vain postuloi, että on olemassa predikaatti joka on tosi tasan silloin kun... jne. Tämä osakaava karakterisoi jälleen transitiivisen sulkeuman.

Tällä operaattorilla voidaan tehdä jo paljon muutakin. Esimerkiksi, voidaan karakterisoida graafissa ns. klikki. Jos p(x,y) on (suuntaamaton) kaarirelaatio, niin \E P(x): \Ax \Ay: (P(x) && P(y)) => p(x,y) && \Ay (\Ax: P(x) => p(x,y)) => P(y). Tämä on tosi predikaatille P(x), jos ja vain jos P(x) on tosi maksimaalisessa sellaisessa joukossa jonka kaikkien solmujen välillä on kaari. Tämän lisäksi täytyy voida jotenkin sanoa että P(x) pätee vähintään jollekin tietylle määrälle alkioita, sivuutan sen tässä teknisenä yksityiskohtana, toivon että lukija luottaa minuun tässä.

On siis mahdollista spesifioida tällä SO[E]-loogikalla se, että graafissa on tietyn kokoinen klikki. Tämä taas on tunnettu NP-täydellinen ongelma, joten SO[E] karakterisoi luokan joka on vähintään NP.

Pienen pohdinnan jälkeen oivalletaan, että jokainen SO[E]-luokan kaava joka on tosi annetulle struktuurille, voidaan osoittaa todeksi ensin arvaamalla tarkalleen milloin nämä uudet predikaatit ovat tosia. Koska jokaisen predikaatin määrittelyssä on jokin vakiomäärä parametrejä (esim k), ja koska syötteenä saadussa struktuurissa on alkioita joihin muuttuja voi viitata vain korkeintaan n kappaletta, on predikaatin totuusarvojoukko kooltaan korkeintaan n^k. Voimme siis arvaamalla nämä uudet predikaatit luoda polynomisessa ajassa FO-kaavan, jonka päteminen alkuperäiselle struktuurille on helppo todeta. Tiedämme siis, että SO[E] = NP.


Kompleksisuushierarkiassa on tästä kompleksisempiakin luokkia, ja lisäksi P-luokan sisällä on paljon alaluokkia. Mutta idea tulee ehkä jo tästä selväksi.