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.

Hyvä harrastus – ja helppo. Lukemista löytyy aina. Kuva: Shutterstock

Kieli rikastuu, ajattelu syvenee ja sosiaalinen taju kehittyy.

Tietokirjan järki on selvä: saa tietoa, jolla jäsentää maailmaa ja vaientaa mutuilijat. Riittävästi tietoa hankkimalla tulee asiantuntijaksi, ja sillä on selvä hyötyarvo.

Entä missä on fiktion lukijan tulosvastuu? Mitä itua on kuluttaa aikaansa tuntitolkulla hatusta vedettyjen ihmisten hatusta vedettyihin edesottamuksiin? Paljonkin: romaani tai novelli opettaa toimimaan muiden ihmisten kanssa.

Fiktio simuloi sosiaalista maailmaa, esittää asiaa tutkinut Toronton yliopiston psykologian professori Keith Oatley. Niin kuin lentosimulaattori opettaa lentotaitoja, sosiaalisten tilanteiden simulaattori – romaani – opettaa sosiaalisia taitoja.

Kokeet vahvistavat, että fiktiota lukeneet tajuavat paremmin so­siaalisia kuvioita kuin tietotekstiä lukeneet. 

Suvaitsevaisuus kasvaa

Kuvitteellisesta tarinasta on sekin ilo, että pääsee väliaikaisesti jonkun toisen nahkoihin. Samastuminen tarinan henkilöön voi muuttaa lukijan käyttäytymistä ja pistää asenteet uusiksi, ovat kokeillaan osoittaneet Ohion yliopiston tutkijat.

Samastumisella on vaaransa. Romaanin aiheuttama itsemurha-aalto koettiin 1700-luvun lopulla, kun nuoret onnettomat miehet matkivat Johan Wolfgang von Goethen päähenkilön tekoa Nuoren Wertherin kärsimyksissä.

Ohiolaistutkimuksessa vaikutus oli rakentavampi: kun nuoret aikuiset olivat lukeneet tarinan miehestä, joka meni äänestämään, he menivät hanakammin vaaliuurnille vielä viikon kuluttua lukemisesta. He olivat saaneet kansalaishyvetartunnan.

Valkoihoisten suvaitsevaisuutta taas kasvattivat tarinat, joissa päähenkilö osoittautui homoseksuaaliksi tai afroamerikkalaiseksi. Lukijoilta karisi myös stereotypioita. Tämä kuitenkin edellytti, että päähenkilön ”erilaisuus” paljastui vasta tarinan myöhemmässä vaiheessa ja lukijat olivat ehtineet asettua hänen nahkoihinsa.

Stressi väistyy

Kun uppoutuu lukemaan, maailman meteli jää kauas ja paineet hellittävät. Tuttu tunne, josta on myös tieteelliset näytöt: lukeminen poistaa stressiä.

Terveystieteen opiskelijat saivat Yhdysvalloissa tehdyssä tutkimuksessa lukeakseen netistä ja aikakauslehdestä poimittuja artikkeleita, jotka käsittelivät historiallisia tapauksia ja tulevaisuuden innovaatioita. Aihepiirit olivat siis kaukana tenttikirjojen pakkolukemistosta.

Puolentunnin lukutuokio riitti laskemaan verenpainetta, sykettä ja stressin tuntua. Huojennus on yhtä suuri kuin samanpituisella joogahetkellä tai televisiohuumorin katselulla. Mikä parasta, apu löytyy helposti, lukemista kun on aina saatavilla.

Sanasto karttuu

Kirjoitettu kieli on ylivoimaisesti suurempi uusien sanojen lähde kuin puhuttu. Erot lasten sanavaraston runsaudessa voi johtaa suoraan siihen, miten paljon he altistuvat erilaisille teksteille, vakuuttavat lukemisen tutkijat Anne Cunningham ja Keith Stanovich.

Tiuhimmin uutta sanastoa kohtaa tieteellisten julkaisujen tiivistelmissä: tuhatta sanaa kohti harvinaisia on peräti 128. Sanoma- ja aikakauslehdissä harvinaisten sanojen tiheys nousee yli 65:n ja aikuisten kirjoissa yli 50:n.

Lastenkirjakin voittaa sanaston monipuolisuudessa televisio-ohjelman mennen tullen. Lapsilukija kohtaa kirjassa yli 30 harvinaista sanaa tuhatta kohti, kun aikuisten telkkariviihdettä katsoessa niitä tulee vastaan 23 ja lastenohjelmissa 20.

Juttelukaan ei pahemmin kartuta sanavarastoa. Aikuispuhe sisältää vain 17 epätavallista sanaa tuhatta kohti.

Syntyy omia ajatuksia

Ihmisen aivoja ei ole ohjelmoitu lukemaan. Kun taito kehittyi 5 500 vuotta sitten, näkemiseen, kuulemiseen, puhumiseen ja ajatteluun rakentuneet alueet alkoivat tehdä uudenlaista yhteistyötä.

Nyt olemme jälleen uudenlaisen lukukulttuurin alussa. Verkkolukeminen on tullut jäädäkseen, ja jotkut pelkäävät, että tyhmistymme, kun totutamme aivomme ärsyketulvaan ja pikaselailuun netissä. Tiedonvälitys on lisääntynyt räjähdysmäisesti mutta niin myös häly.

Syventyvän lukemisen kohtalosta kantaa huolta professori Maryanne Wolf Tufts-yliopistosta. Tapaa näet kannattaisi vaalia. Aivokuvaukset paljastavat, että paneutuva lukija käyttää laajasti molempia aivopuoliskojaan. Hän ei vain vastaanota kirjoittajan sanomaa vaan vertaa sitä aiemmin hankkimaansa tietoon, erittelee sitä ja rakentaa omaa ajatteluaan. Pintalukijalla ei tähän ole aikaa.

Mikko Puttonen on Tiede-lehden toimittaja.

Julkaistu Tiede-lehdessä 12/2012 

Täysin raittiiden suomalaisnuorten osuus on moninkertaistunut vuosituhannen alusta.

Nuoruus raitistuu, kertoo Helsingin Sanomat jutussaan.

Nuorten alkoholin käyttö kasvoi vuoteen 1999, joka oli myös kaikkein kostein vuosi. Silloin vain joka kymmenes yhdeksäsluokkalainen ilmoitti, ettei ollut koskaan käyttänyt alkoholia.

Sittemmin täysin raittiiden osuus on moninkertaistunut, ilmenee vuoteen 2015 ulottuneesta eurooppalaisesta, nuorten päihteidenkäyttöä käsittelevästä Espad-tutkimuksesta.

Jopa muut eurooppalaiset jäävät jälkeen. Suomessa täysin raittiita 15–16-vuotiaista nuorista on joka neljäs, kun Euroopassa heitä on keskimäärin joka viides.

Terveyden ja hyvinvoinnin laitoksen THL:n erikoistutkija Kirsimarja Raitasalo kollegoineen on ­koettanut tunnistaa niitä nuoruuden muutoksia, jotka voisivat selittää humalan hiipumista.

Ratkaisevaa näyttää olleen ainakin se, että alaikäisten on yhä vaikeampi saada alkoholia. Nykynuoret kokevat sen selvästi hankalammaksi kuin aiemmat ikäpolvet.

Kauppojen omavalvonta on osaltaan tehonnut. Kassoilla kysytään kaikilta alle 30-vuotiaan näköisiltä papereita.

Vanhemmat ja muutkin aikuiset ovat tiukentaneet asenteitaan nuorten juomiseen.

”Tietoisuus alkoholin haitoista on ehkä lisääntynyt. On tullut paljon tutkimustietoa esimerkiksi siitä, miten alkoholi vaikuttaa nuorten aivojen kehitykseen”, Raitasalo pohtii.

Nuorten omakin maailma on muuttunut toisenlaiseksi. Älylaitteet, pelit ja sosiaalinen media kyllästävät arkea. Pussikaljoittelu joutuu kilpailemaan monen muun kiinnostavan ajanvietteen kanssa ja on ehkä osittain hävinnyt niille.

Juovuksissa olemisesta on ehkä tullut myös tyylirikko. Nuoret eivät enää näytä arvostavan kännissä örveltämistä.

Kysely

Mikä mielestäsi raitistaa nuoria?

Neutroni
Seuraa 
Viestejä25784
Liittynyt16.3.2005

Viikon gallup: Mikä mielestäsi raitistaa nuoria?

Käyttäjä4809 kirjoitti: Eiköhän syy ole -90 luvulla alkaneen laman menetetyt työpaikat ja samalla supistettu koulutus, minkä seurauksena vuodestä -99 alkaen vanhemmilla ei enää ole ollut niin paljon rahaa annettavaksi nuorisolle. Sekä myös nuorisolle soveltuvien työpaikkojen vähentyminen ja samaan aikaan tapahtunut kohtuuton vuokrien nousu, vasinkin pääkaupunkiseudulla. En tiedä, mutta en usko rahaan. Esimerkiksi kilju, 10 % juoma joka maksaa joitain senttejä litralta, tuntuu olevan...
Lue kommentti
molaine
Seuraa 
Viestejä1189
Liittynyt3.8.2011

Viikon gallup: Mikä mielestäsi raitistaa nuoria?

En kyllä usko, että rahalla on iso merkitys ja veikkaan, että käytettävissä olevat rahat on vain kasvaneet, jos verrataan vaikka omaan nuoruuteen. Ei viina suomessa ole niin kallista, etteikö köyhälläkin olisi varaa dokailla. Oma junnu ei läträä lainkaan viinan kanssa. Iso osa kavereistakaan ei, vaikka osa ilmeisesti jonkin verran lipittelee. Kyllä nuorten asenteet on mielestäni muuttuneet ihan selkeästi. Ehkä alkoholipolitiikka on toiminut? Kotoa ei meillä kyllä tällaista ole opittu...
Lue kommentti

Panterarosa: On selvää, että "Partitava kisaa kurupati-kuvaa" ei oikein aukene kehitysmaalaisille N1c- kalmukinperseille.