Jos hän keksii nopean tavan sen laskemiseen, hän tulee samalla ratkaisseeksi kuuluisan matematiikan ongelman: voidaanko kaikki sellaiset ongelmat, joiden ratkaisut voi tarkistaa helposti, myös ratkaista helposti?  

Teksti: Kaisa Kangas

Kauppamatkustajalla on lista kaupungeista, joissa hän aikoo myydä tuotteitaan. Hän haluaa käydä jokaisessa kaupungissa mutta käyttää matkaansa mahdollisimman vähän aikaa. Hän yrittää siis etsiä lyhimmän mahdollisen reitin, joka kulkee jokaisen kaupungin kautta. Periaatteessa se on helppo löytää: lasketaan kaikkien mahdollisten reittien pituudet ja valitaan niiden joukosta lyhin. Kun listalle lisätään uusia kaupunkeja, mahdollisten reittien määrä kuitenkin kasvaa huimaa vauhtia ja laskuihin menee enemmän ja enemmän aikaa. Jos kaupunkeja on kaksi, on reittejäkin periaatteessa kaksi. Kauppamatkustaja voi lähteä jommastakummasta kaupungista ja edetä jäljellä olevaan. Jos kaupunkeja on neljä, saadaan 4 x 3 x 2 x 1 eli 24 mahdollista reittiä joista valita. Mutta jo 20 kaupungin tapauksessa reittejä on noin 2,4 triljoonaa (2 400 000 000 000), ja laskujen laskeminen käy niin hankalaksi, että olisi parempi valita reitti umpimähkään. Jos globaalia bisnestä pyörittävä kauppamatkustaja joutuu käymään retkillään kymmenissätuhansissa kaupungeissa, ei nopeinkaan supertietokone pysty laskemaan kaikkia reittejä. Kauppamatkustajan ongelmaan liittyvä ydinkysymys onkin, onko olemassa jokin menetelmä, jolla lyhin reitti löytyisi kohtalaisen nopeasti.

Sovelluksia geenitutkimukseen

Kauppamatkustajan ongelma ei ole pelkkä ajatuspähkinä. Lyhyiden reittien etsimisestä on hyötyä erityisesti logistiikkaan ja kuljetuksiin liittyvissä sovelluksissa. Esimerkiksi sanomalehtien jakelureittejä suunniteltaessa on kustannustehokasta etsiä mahdollisimman lyhyt tai muuten nopea reitti, jolla lehdenjakaja tulee käyneeksi jakelualueellaan jokaisessa talossa, johon lehti on tilattu. Sovelluksia löytyy myös muilta aloilta. Mikrosirujen valmistuskustannusten kannalta voi olla ratkaisevaa, missä järjestyksessä siruihin porataan niiden lukuisat pienet reiät. Kauppamatkustajan ongelmaa muistuttavaan tilanteeseen päätyy myös geenitutkija, joka yrittää yhdistää kokoelman dna-ketjuja yhdeksi, mahdollisimman lyhyeksi ketjuksi. Avaruusteknologiassa ongelma nousee esiin kun määritetään, missä järjestyksessä kannattaa suorittaa tähtitieteellisiä mittauksia kahdesta erillisestä satelliitista koostuvalla järjestelmällä.

Ensiksi naapuriin

Kun reittejä etsitään käytännön tarpeisiin, riittää usein, että ne ovat lyhyitä tai että niiden kulut ovat hyväksyttävissä rajoissa. Ei siis ole aina välttämätöntä löytää kaikkein lyhintä tai nopeinta reittiä. Onkin kehitetty menetelmiä, joilla voidaan laskea miljoonien kaupunkien verkostosta nopeasti reittejä, jotka todennäköisesti ovat paljon lyhempiä kuin valtaosa muista reiteistä. Näiden menetelmien tuottamat reitit ovat suurella todennäköisyydellä lyhimpien mahdollisten joukossa, mutta erehtymisen vaara on olemassa.Eräs yksinkertainen tapa etsiä lyhyitä reittejä on niin sanottu lähimmän naapurin menetelmä. Aina saavuttuaan uuteen kaupunkiin kauppamatkustaja viivaa sen yli listaltaan ja käy läpi jäljellä olevat kaupungit. Hän valitsee niiden joukosta sen, johon on lyhin matka, ja matkustaa sinne. Tällä tavoin reitti jää yleensä kohtalaisen lyhyeksi, eikä kauppamatkustaja joudu laskemaan monimutkaisia laskuja. On kuitenkin olemassa sellaisia – joskin harvinaisia – kaupunkien sijoitteluita, joissa lähimmän naapurin menetelmä tuottaa pisimmän mahdollisen reitin.

Miljoonan dollarin ongelma

Vuonna 2000 amerikkalainen matematiikkainstituutti Clay Mathematics Institute juhlisti uutta vuosituhatta julkaisemalla listan seitsemästä vaikeasta ja merkittävästä matemaattisesta ongelmasta. Kunkin ongelman ratkaisijalle se lupasi miljoonan dollarin suuruisen Millennium-palkinnon. Vuonna 2002 venäläinen Grigori Perelman ratkaisi ensimmäisen todistaessaan Poincarén konjektuurina tunnetun otaksuman, mutta loput kuusi ongelmaa odottavat edelleen ratkaisijaansa. On osoittautunut, että jos joku keksii nopean tavan ratkaista kauppamatkustajan ongelma, hän on samalla löytänyt vastauksen yhteen jäljellä olevista Millennium-ongelmista. Se tunnetaan nimellä P versus NP, ja sitä pidetään teoreettisen tietojenkäsittelytieteen merkittävimpänä avoimena ongelmana. Kysymys kuuluu, onko nimellä P tunnettu joukko kohtalaisen helppoja tehtäviä (helpolla tarkoitetaan, että tietokone pystyy laskemaan ne nopeasti) sama kuin nimellä NP tunnettu joukko tehtäviä, joiden ratkaiseminen saattaa olla vaativaa (eli siihen menee tietokoneella kauan), mutta joiden ratkaisut on helppo tarkistaa. Mikäli nämä tehtäväluokat olisivat samat, monia hankalina pidettyjä tehtäviä pystyttäisiinkin ratkaisemaan nopeasti.Joukkoon NP kuuluu esimerkiksi eräs versio kauppamatkustajan ongelmasta. Nyt ei etsitä lyhintä reittiä, vaan kysytään, onko olemassa reitti, joka on korkeintaan tietyn tavoitearvon, esimerkiksi 2 000 kilometrin, mittainen. Yksi tapa lähestyä ongelmaa on valita jokin reitti, joka intuitiivisesti tuntuu lyhyeltä, ja laskea sen pituus. Mikäli arvaus on hyvä ja reitin pituus alittaa tavoitearvon, olemme ratkaisseet ongelman nopeasti. Pahimmassa mahdollisessa tapauksessa joudumme kuitenkin laskemaan tuskallisen monta reittiä ennen kuin löydämme tarpeeksi lyhyen reitin, ja jos tavoitearvon alittavaa reittiä ei ole olemassa, joudumme laskemaan kaikki reitit. On siis helppo tarkistaa, onko arvattu reitti ongelman ratkaisu, mutta itse ongelman ratkaisemiseen ei tiedetä nopeaa keinoa. Joukolla NP tarkoitetaankin sellaisia tehtäviä, joiden tapauksessa tietokone pystyy nopeasti tarkistamaan, onko ehdotettu ratkaisu oikea. P versus NP -ongelma voidaan kansanomaisemmin muotoilla seuraavasti: ”Voidaanko kaikki sellaiset ongelmat, joiden ratkaisut voi helposti tarkistaa, myös ratkaista helposti?”

Rikkaaksi Miinaharavalla

Yllä kuvattu versio kauppamatkustajan ongelmasta on niin sanottu NP-täydellinen ongelma. Tämä tarkoittaa, että mikäli löytyisi nopea tapa ratkaista kyseinen ongelma, olisivat kaikki muutkin joukossa NP olevat tehtävät nopeasti ratkaistavissa. Tällöin joukot P ja NP olisivat samat – tulos, jonka todistamisesta ansaitsee miljoonan dollarin palkinnon! Yksinkertaiselta kuulostavan kauppamatkustajan ongelman ratkaisija olisi samalla osoittanut jotakin perustavanlaatuista lukuisten erilaisten ongelmien luonteesta.Kauppamatkustajan ongelma ei ole tässä suhteessa ainutlaatuinen, vaan NP-täydellisiä ongelmia on muitakin. Yksi niistä liittyy Microsoftin Windows-järjestelmän kylkiäisenä tulevaan Miinaharava-peliin. Miljoonan dollarin palkinnon voi netota kehittämällä tehokkaan tavan ratkaista pelin strategisia tilanteita. Pelkkä Miinaharavassa pärjääminen tai edes pelin voittaminen ei kuitenkaan valitettavasti riitä. On keksittävä yleispätevä strategia, jota voi soveltaa kohtalaisen nopeasti, vaikka pelikenttä kattaisi miljoonia ruutuja. Miljoonapalkinto on luvassa myös, jos pystyy todistamaan ettei ole olemassa tehokasta Miinaharava-strategiaa tai nopeaa tapaa ratkaista kauppamatkustajan ongelma. Tällöinhän olisi löydetty joukosta NP sellainen ongelma, joka ei olisi nopeasti ratkaistavia ongelmia sisältävässä joukossa P, eivätkä nämä kaksi joukkoa siis voisi olla samat. Ennen kuin alkaa hioa Miinaharava-strategiaansa täydellisyyksiin, kannattaakin huomioida, että useimmat alan asiantuntijat uskovat, että joukot P ja NP eivät ole samat.Arvostetun Massachusettsin teknisen yliopiston MIT:n tietojenkäsittelytieteilijä Scott Aaronson on todennut, ettei yleisten käsitystemme kanssa sovi yhteen ajatus siitä, että ongelmien ratkaiseminen on yhtä helppoa kuin ratkaisujen tarkistaminen. Mikäli näin olisi, ratkaisemisen ja ratkaisun ymmärtämisen prosessit eivät juuri eroaisi toisistaan. Tällöin voisi yhtä hyvin ajatella, ettei säveltäminen ole sen vaikeampaa kuin sinfoniakonsertista nauttiminen. Toisaalta Aaronson voi olla väärässäkin, sillä matematiikka on ennenkin kumonnut yleisiä käsityksiä päälaelleen.

Ratkaisuyritys elokuussa

Viime elokuun alussa intialainen Vinay Deolalikar julkisti yli satasivuisen artikkelin, joka herätti suurta kohua internetissä. Deolalikar väitti todistaneensa, että joukot P ja NP eivät ole samat, mikä oikeuttaisi hänet miljoonan dollarin palkintoon. Miltei välittömästi Scott Aaronson lupasi myydä talonsa ja lisätä omista varoistaan 200 000 dollaria Millennium-rahoihin, jos Deolalikarin todistus osoittautuu vedenpitäväksi. Aaronson kirjoitti blogissaan, että mikäli ongelma todella olisi ratkaistu, talosta luopuminen olisi pienin muutos hänen elämässään, sillä koko hänen tutkimusalansa on tähän asti pyörinyt ongelman ympärillä. Pian asiantuntijat löysivätkin todistuksesta virheitä, joiden korjaaminen vaatisi ratkaisevia uusia ideoita. Kysymys on siis vielä toistaiseksi avoinna. Miljoonapalkinto odottaa ottajaansa!

Kaisa Kangas on matematiikan jatko-opiskelija, filosofian maisteri ja humanististen tieteiden kandidaatti.

Julkaistu Tiede -lehdessä 1/2011.