Tietojenkäsittelyteorian osa-alue kompleksisuusteoria käsittelee sitä, miten vaikeaa jokin laskutehtävä on ratkaista. Tässä täytyy käyttää aina oletuksia siitä miten laskenta etenee ja toisaalta abstraktioita joiden taakse piilotetaan yksityiskohtia, koska muutoin teoria menee tavattoman monimutkaiseksi.
Suuri osa varsinaista teoriaa on epistemologisesti ajatellen triviaalia. On kuitenkin joitakin ongelmia, ja erityisesti ratkaisuja, jotka tuovat mielenkiintoisia yhteyksiä empiirisen tieteen filosofian ja epistemologian pariin.
Yksi näistä on kompleksisuusluokka nimeltä IP, joka tulee sanoista "interactive polynomial time". Tyypillisissä abstraktioissa polynomiaikaisuutta pidetään "järkevästi" ratkaistavien ongelmien määritelmänä; en nyt lähde tätä problematisoimaan, siihen pätee tiettyjä ehtoja ja edellytyksiä yms, jätän netoiseen kirjoitukseen.
Intreaktiivisuus tässä kompleksisuusluokassa voidaan esittää näin: meillä on äärimmäisen tehokas -- maaginen, jos niin halutaan -- mustana laatikkona annettu tietokone tms, oraakkeli, joka vastaa aina oikein kaikenlaisiin kysymyksiin. Ongelmana on se, että oraakkelin vastaus sinänsä ei kelpaa meille todisteeksi, sillä emme usko taikuuteen, vaan sen pitää antaa meille paitsi vastaus, myös todistus siitä, että vastaus on oikea.
Esimerkiksi, jos kysymme että "voiko annettu logiikan kaava olla tosi?", ei riitä, että oraakkeli vastaa "kyllä", vaan oraakkelin pitää kyetä antamaan jokin todiste siitä, että kaava todella voi olla tosi; tässä tapauksessa oraakkeli voi antaa sellaisen, jos "kyllä" oikeasti on oikea vastaus, näyttämällä että kaavalla on malli. Tämän jälkeen voimme polynomisessa ajassa tarkastaa että todistus on oikein.
Jos rajoitumme ongelmiin joiden ratkaisemiseksi voimme kysyä vain yhden kysymyksen, ja meidän täytyy pystyä tarkastamaan vain "kyllä"- vastaus polynomisessa ajassa, saamme tutun luokan NP. Sensijaan jos voimme esittää toistuvasti kysymyksiä, ja voimme rakentaa satunnaisgeneraattoria käyttävän koneen, joka polynomisella määrällä kysymyksiä (ja polynomisessa ajassa) vakuuttumaan niin, että virheellisen vastauksen todennäköisyys voidaan tehdä mielivaltaisen pieneksi, niin saamme luokan IP.
Otetaan esimerkki, jota usein käytetään, NP-ongelmasta (tosin ei NP-täydellisestä) joka toimii hyvin IP:n havainnollistamiseksi: Graafien isomorfismi. Graafi-isomorfismi tarkoittaa, että jos meillä on kaksi graafia, voidaanko antaa rakenteellinen isomorfismi näiden graafien solmuille, so. ovatko graafit solmujen ja kaarien nimiä lukuunottamatta täysin samanlaiset. Jos vastaus on "kyllä", tämä on helppo osoittaa antamalla pareittain ne solmut jotka kuvautuvat isomorfismissa toisikseen. Jos vastaus on "ei", mitään tällaista ilmeistä todistetta ei ole -- moniin ei-tapauksiin toki on todisteita, muttei tunneta todistetta joka takaa että graafit eivät ole isomorfiset siten, että kaikilla ei-isomorfisilla graafeilla on tämä todiste.
IP:ssä voimme kuitenkin melko helposti ratkaista tämän. Annamme oraakkelille kaksi graafia ja kysymme, ovatko ne isomorfiset; jos vastaus on kyllä, oraakkeli antaa meille todisteen. Jos vastaus on "ei", me aloitamme kyselykierroksen. Käytämme satunnaislukugeneraattoria ja "sekoitamme" kummankin graafin solmut ja kaaret. Tämän jälkeen valitsemme satunnaisest jomman kumman graafin ja kysymme, "kumpi alkuperäisistä graafeista tämä on?". Jos graafit oikeasti ovat isomorfiset, oraakkeli ei voi tätä tietää mitenkään, joten sen vastaus on olennaisesti satunnainen. Jos graafit taas eivät ole isomorfisia, oraakkeli antaa aina oikean vastauksen. Toistamme tämän arvonnan uudelleen ja uudelleen, ja jos oraakkeli joka kerta vastaa oikein, luottamuksemme oraakkelin alkuperäiseen vastaukseen kasvaa. Jos päätämme ennalta minkä hyvänsä todennäköisyyden, voimme esittää kysymyksen riittävän monta kertaa jotta saamme virheen todennäköisyyden tätä rajaa pienemmäksi.
Mikä tekee IP:n mielenkiintoiseksi on, että sen tiedetään olevan tarkalleen sama kuin kompleksisuusluokka PSPACE, eli polynomisen muistirajoitteen kanssa ratkeavien ongelmien luokka. Tähän luokkaan kuuluvat (pienin viilauksin) esimerkiksi yleistykset useimmista kahden pelaajan peleistä. Pelimetafora ei ole tässä sattumaa; oraakkeli voi ratkaista jokaisen kahden pelaajan pelin sen kummemmitta ongelmitta. Jos oraakkeli sanoo mistä hyvänsä kahden pelaajan pelistä että "tämä asema on voittava pelaajalle X", niin oraakkeli myös voittaa kaikki pelit jotka siitä asemasta pelataan jos se saa pelata pelaajan X puolesta. Jos pelin pituus on polynominen pelin esitystapaan nähden, niin tämä "todiste" voidaan pelata läpi polynomisessa ajassa. Jos itse peli on ratkeava polynomisessa tilassa, voidaan pelejä simuloida "riittävän monta" vakuuttuaksemme siitä että oraakkeli todellakin on voittamaton.
Tätä voidaan heijastella myös siis empiiriseen tieteeseen. Operationalisoinnin jälkeen "tarkastamme" teorian ennusteen saadaksemme luottamusta siihen että teorian antama ennuste on oikea. Jos kysymyksenasettelu ja abstraktio ovat oikein ja tarkoituksenmukaisesti rajattu -- ja tämä on se iso "jos" -- niin voimme vakuuttua että teoria antaa vastauksen kysymykseen "oikein". Teoria itsessään ei ole sen paremmin oikea kuin vääräkään, joskin useimmiten sanoisimme että se on väärä, jos se antaa systemaattisesti satunnaisia ennusteita, so. ennusteita joissa ei ole mitään informaatiota itse ilmiöstä.
Ei kommentteja:
Lähetä kommentti