VIRKAANASTUJAISESITELMÄ
2.12.1998
Turun yliopisto
Tietojenkäsittelytieteestä onkin muodostunut matemaattisen tutkimuksen keskeinen motivaation lähde. Turun yliopistossa tämän yhteyden tärkeys oivallettiin jo yli 30 vuotta sitten professori Salomaan luodessa matemaatiikan laitokselle automaattien teorian koulukunnan. Vielä tänäkin päivänä matematiikka ja tietojenkäsittelytiede ovat Turun yliopistossa samalla laitoksella - päinvastoin kuin muissa maamme korkeakouluissa.
Huomattava osa matemaattista tutkimusta on aina ollut käytännön tai muiden tieteenalojen motivoimaa. Ensimmäisten korkeakulttuurien aikoina motivaatio tuli tarpeesta laatia kalenteri tai jakaa viljelymaat. Newtonin ajoista lähtien tärkein motivaation lähde on ollut fysiikka, halu ymmärtää ja selittää fysiikan lainalaisuuksia. Myöhemmin monet muut tieteenalat ovat tulleet fysiikan rinnalle, mutta eivät ole pystyneet horjuttamaan fysiikan valta-asemaa. Nyt tietojenkäsittelytiede on tekemässä näin.
Viime vuosikymmeninä matematiikkaan on tämän vuoksi tullut aivan uusia painotuksia. Algoritminen matematiikka on noussut entistä keskeisemmäksi. On syntynyt kokonaan uusia aloja, kuten automaattien teoria, algoritmien kompleksisuusteoria tai laskettavuuden teoria - vain joitakin mainitakseni. Lisäksi monille vanhoille aloille on syntynyt uusia osa-alueista, kuten algoritminen lukuteoria. Diskreetin matematiikan korostuminen on toinen selkeä - ja helposti miellettävä - muutos. Tietokoneen lasku koostuu aina yksittäisistä laskuaskeleista. Näitä voi olla tuhat, miljardi tai tuhatmiljardia aikayksikössä, mutta kutakin laskua kohden aina vain äärellinen määrä. Pienempää aikayksikköä kuin laskusaskeleen vaatima aika ei ole. Näinollen tietokoneen tai sen laskun mallintaminen johtaa väistämättä diskreettiin ongelmanasetteluun.
Tarkemmin analysoituna tietokoneet operoivat symboleilla 0 ja 1, tai hieman yleisemmin symbolijonoilla eli sanoilla. Näin myös silloin, kun ne laskevat luvuilla. Toisaalta, myös tietokoneen ohjelma on matemaattisesti vain jono symboleja. Symbolijonojen eli sanojen ominaisuuksien tutkiminen - sanojen kombinatoriikka - onkin muodostunut tärkeäksi, ja erittäin haastavaksi matematiikan uudeksi tutkimusalueeksi. Alan tutkimus on ensi sijassa matemaattista perustutkimusta, jolla on kuitenkin runsaasti sovellusmahdollisuuksia.
Mainitsen yhden konkreettisen esimerkin. Etsitään tiettyyn hakusanaan, esim. "NP-complite", liityviä julkaisuja jostakin kirjaston tietokannasta. Kone siis hakee kaikki julkaisut, joissa sana "NP-complite" esiintyy otsakkeessa, avainsanana tai tiivistelmässä. Miten kone voi tulostaa kaikki, tässä tapauksessa noin 6000, julkaisua vain kohtullisella viivellä? Osan, mutta vain osan, tästä selittää nykytietokoneiden suunnaton teho. Matemaattisesti kiehtovimman osan selitystä muodostaa etsintämetodi: käytetään nopeaa - esim. lineaarisessa ajassa toimivaa - algoritmia sanan, siis symbolijonon etsimiseksi tekstistä. Tällaiset algoritmit perustuvat täysin sanojen kombinatorisiin ominaisuuksiin. Muina sanojen kombinatoriikkan sovellutuksina voisi mainita kaiksiulotteisten digitaalisten kuvien tiivistämisen tai diskreettien kaoottisten ilmiöden tutkimisen.
Tarkastelen seuraavassa joitakin mainittujen matematiikan uusien suuntausten saavuttamia syvällisiä tuloksia.
Jo 1930-luvulla - tietokoneiden aikakauden vasta sarastaessa - itävaltalainen matemaatikko Kurt Gödel, yhdessä eräiden aikalaistensa kanssa, paljasti tämän vuosisadan merkittävimpiin kuuluvan matemaattisen totuuden: algoritmisen ratkeamattomuuden. Toisin sanoen sen, että on olemassa probleemoja, joita ei voida edes periaatteessa - olipa laskuaikaa tai muistitilaa kuinka paljon tahansa - ratkaista tietokoneella. Ne ovat ja pysyvät tietokoneiden saavuttamattomissa.
Keksintö oli käänteentekevä matematiikan historiassa . Se osoitti, ettei edes matematiikka ole täsmällisesti formalisoitavissa, kuten hänen opettajansa David Hilbert oli vuosisadan alussa unelmoinut. Itse asiassa Hilbertin aikalaisille ei tullut edes mieleen se mahdollisuus, että olisi olemassa probleemoja, jotka ovat todistettavasti mahdottomia ratkaista algoritmisesti. Nykyiset Turun yliopiston matematiikan, ja myös tietojenkäsittelytieteen, opiskelijat oppivat asioita, jotka olivat tuntemattomia, jopa uskomattomia, vuosisatamme suurimpiin kuuluvalle matemaatikolle vielä 1900-luvun alussa.
Algoritmisesti ratkeamattomat probleemat eivät itse asiassa ole lainkaan harvinaisia. Esimerkkinä tällaisesta mainitsen kysymyksen: toimiiko annettu tietokoneohjelma oikein? Myös monet matematiikan perusongelmat ovat algoritmisesti ratkeamattomia. Tällaisia ovat esimerkiksi kysymykset "Onko äärellisesti generoitu kokonaislukualkioisten matriisien multiplikatiivinen puoliryhmä vapaa tai sisältääkö se nolla-alkion?" Ratkeamattomuus pitää paikkansa myös 3*3-matriiseille, joten jälkimmäinen probleema voidaan tulkita kysymyksenä "Saadaanko kolmiuloitteisen avaruuden äärellisen monen lineaarikuvauksen jonkinlaisena tulona nollakuvaus?" Tämän kysymyksen selvittämiseksi ei siis ole olemassa algoritmia.
Tarkastelin edellä probleemojen ratkeavuutta asettamatta mitään rajoituksia laskuajalle tai tarvittavien muistipaikkojen lukumäärälle, siis hyvin teoreettisesti. Siirryn seuraavassa astetta käytännöllisempiin kysymyksiin.
Eräs käytännön elämässä vastaantuleva ongelma on lukujärjestyksen laatiminen. Koulumaailman termein lähtökohdana on tietty määrä opettajia, oppilasryhmiä, luokkahuoneita jne, sekä tehtävänä laatia, jos mahdollista, "hyvä" lukujärjestys. Jätän termin hyvä tarkemmin määrittelemättä, mutta vaatimuksena on esimerkiksi se, että kukaan opettaja ei ole kahdessa luokassa samanaikaisesti.
Klassisen matematiikan näkökulmasta probleema on triviaali: kokeillaan kaikkia mahdollisuuksia, joita on äärellinen määrä, ja valitaan näistä "hyvä", jos sellainen löytyy. Probleeman ratkaisemiseksi on siis olemassa yksinkertainen metodi. Käytännössä metodi ei kuitenkaan toimi: vaikka lukujärjestyksen laatijalla olisi käytössään supertietokone, niin aivan reaalista kokoa olevan koulun "riitävän hyvä" lukujärjestys voisi olla laatimatta lukuvuoden jo päätyttyä. Tarkasteltavia tapauksia on liian paljon.
Voidaanko probleema ratkaista käytönnössä jollain muulla metodilla, siis algoritmilla, joka toimii syötteen kokoon nähden polynomaalisella määrällä operaatioita? Kysymykseen ei tiedetä vastausta. Se, mikä oli matemaattisesti triviaalia, onkin käytännössä laskennallisesti mahdotonta - nykytiedon mukaan!
Vastaus mainittuun kysymykseen on - luonnollisesti - "kyllä" tai "ei". Kummassakin tapauksessa tuloksen seuraukset ovat mullistavia: Jos polynomiaikainen algoritmi löydetään, niin samalla löydetään polynomiaikainen algoritmi monille klassisen matematiikan peruskysymyksille, kuten esimerkiksi "Onko annettu luku alkuluku?" tai "Miten luku voidaan jakaa alkutekijöihinsä?" Toisaalta, jos vastaus on "ei" niin monet tärkeät käytännön kysymykset, kuten esim. optimaalisen ruokalistan laatiminen tietyllä rahamäärällä, tulevat mahdottomiksi ratkaista.
Esitetty lukujärjestyksen laatimisprobleema on esimerkki nk. NP-täydellisestä probleemasta. Yksi nykymatematiikan tärkeimmistä avoimista kysymyksistä kuuluu: onko NP-täydellisillä probleemoilla polynomiajassa toimivaa algoritmista ratkaisua? Tavallisesti probleema formuloidaan kysymyksenä "Onko P yhtä kuin NP?", kuten pohjoisamerikkalaiset tutkijat Stephen Cook ja Richard Karp sen 1970-luvun alussa muotoilivat.
Matemaattisesti P=NP-probleema kysyy, onko jokainen probleema, joka voidaan ratkaista epädeterministisellä polynomiajassa toimivalla algoritmilla ratkaistavissa myös deterministisesti polynomiajassa. En määrittele yksityiskohtaisesti mitä - pitkälti intuition vastaisella - epädeterministisellä algorimilla tarkoitetaan, mutta havainnollistan sitä esimerkillä. Oletetaan, että oppilailla on laskettavanaan jokin matematiikan harjoitustehtävä. Oppilas D ratkaisee tehtävän itsenäisesti, siis etsii itse ratkaisun. Oppilas N puolestaan turvautuu kaverinsa kykyihin, kopio tältä ratkaisun, mutta siltä varalta, että joutuu esittämään sen opettajalleen, haluaa varmistua, että ratkaisu on oikea, siis verifioi sen itselleen. Kumpi löytää ratkaisun nopeammin: oppilas D, jonka on löydettävä ratkaisu ja todettava se oikeaksi, vai oppilas N, joka saa ratkaisun ja joutuu vain toteamaan sen oikeaksi. Jos tehtävä on matemaattisesti onnistunut, vastaus on selvä: N selviää nopeammin. Tässä N toimii kuten epädeterministiset algoritmit: hän arvaa, kaverinsa avulla, ratkaisun, jolloin hänen täytyy vain varmistua ratkaisun oikeellisuudesta.
Annetussa esimerkissä epädeterministinen metodi tuntuu intuitiivisesti selvästi nopeammalta. Yhtälailla olisi intuition mukaista veikata, että P¹NP, mutta tätä ei siis ole onnistuttu todistamaan.
Perustelin jo aiemmin miksi P=NP-probleema on äärimmäisen tärkeä. Probleeman haastavuutta osoittaa siihen uhrattu tutkimuspanos. Mainitsin aiemmin avainsanalla NP-complite suoritetun tietokantahaun. Esimerkki ei ollut fiktiota, vaan todella kyseinen haku Kalifornian yliopiston tietokannassa tuotti noin 6000 julkaisua - vuodessa.
Tosiasia, että monille tärkeille käytönnön probleemoille ei tunneta polynomiaikaista ratkaisumetodia, voi tuntua masentavalta, ja sitä se tietysti prakmaatikolle onkin. Mutta luoville matemaatikoille se tarjoaa aivan uusia ulottuvuuksia. 1970-luvun lopulla kehitetty yksisuuntaisen funktion käsite on oiva esimerkki tästä. Tällaisen funktion arvon laskeminen on "helppoa", mutta käänteisfunktion arvon laskeminen on "mahdotonta". Tässä "helppo" viittaa polynomiaikaiseen laskuun ja "mahdoton" tämän vastakohtaan. Kahden alkuluvun tulon laskeminen on esimerkki yksisuuntaisesta funktiosta. Lukujen tulon laskeminen - vaikka luvut olisivat käsittämättömän suuria, esim. noin 200-numeroisia - onnistuu nykytietokoneilla hetkessä. Toisaalta kukaan ei tiedä, miten saatu noin 400-numeroinen luku voitaisiin jakaa tekijöihinsä edes vuosien laskuilla! Funktio on siten yksisuuntainen - matemaattisen nykytiedon valossa. Tällaisia käytännössä yksisuuntaisia funktioita tunnetaan monia muitakin. Ei kuitenkaan tiedetä - ja tämä on yksi matematiikan suuria haasteita - onko olemassa todistettavasti yksisuuntaisia funktioita.
Kuvaillut käytännössä yksisuuntaiset funktiot tarjoavat
hämmästyttäviä uusia kommunikointimahdollisuuksia
tietoverkoissa. Tarkastelen seuraavassa lyhyesti yhtä, ehkä
kaikkein kiehtovinta mahdollisuutta, nk. nollatietotodistusta.
Tässä kaksi osapuolta T(odistaja) ja V(astaanottaja) kommunikoivat keskenään tietoverkossa. Alussa T tietää tietyn asian, esim tietokoneen salasanan, mutta V, siis kone, ei sitä tunne. T:n tavoitteena on todistaa tietävänsä salasanansa kirjoittamatta sitä. Miten tämä on mahdollista? Vastauksen tarjoaa yksisuuntaisen funktion sopiva käyttö. Menemättä yksityiskohtiin kone V esittä T:lle joitakin kysymyksiä, joihin T vastaa. Vastausten perusteella kone tulee vakuuttuneeksi siitä, että T todella tietää salasanansa, mutta V ei sitä opi. Olellista on myös se että kukaan ulkopuolinen ei pysty vastaamaan koneen V kysymyksiin oikein, siis vakuuttamaan konetta siitä, että hän tuntisi T:n salasanan. Kuvailtu tilanne on todella realisoitavissa. Yhteys viime aikoina mieliä kuohuttaneeseen pankkikorttihuijaukseen on kiintoisa. Toteuttamalla asiakkaan ja pankkiautomaatin kommunikointi nollatietotodistuksella vältytään salasanan kirjoittamiselta, ja siten huijaus, joka perustuu salasanan jonkinlaiseen kaappaamiseen, tulee mahdottomaksi.
Korostin alussa tietojenkäsittelytiedettä matemaattisen tutkimuksen motivaation lähteenä. Fysiikan, tai jopa biologian, merkitystä algoritmisen matematiikan kehitykselle ei kuitenkaan voi unohtaa. Kvantti- ja DNA-laskenta ovat tästä tervetulleita muistutuksia. Viime vuosien kiehtova oivallus on ollut ajatus käyttää kvanttimekaniikan lainalaisuuksia algoritmisen laskemisen toteuttamiseen. Se, onnistutaanko nk. kvanttitietokone joskus rakentamaan, on fyysikkojen ja insinöörien haaste. Matemaatikkojen haaste on se, mitä tällaisella konella voitaisiin laskea. Amerikkalainen Peter Shor hätkähdytti tiedemailmaa vuonna 1994 osoittamalla, että luvun tekijöihinjako voidaan suorittaa polynomiajassa kvanttikoneella. Voidaanko lukujärjestyksen laatimisprobleema, tai jokin muu NP-täydellinen probleema, niin ikään ratkaista polynomiajassa kvanttitietokoneella, on yksi tulevaisuuden suuria haasteita.
Olen tarkastellut matemaattisen tutkimuksen eräitä huomattavia saavutuksia ja niiden avaamia uusia hasteita. Kaikki mainitut tulokset - Gödelin töitä lukuunottamatta - on saavutettu niinä vuosina tai sen jälkeen, kun Turun yliopistoon nimitettiin edelliset matematiikan professorit. Matemaatikot eivät ole kaavoihinsa kangistuneita.