Viikonloppuna puukkomies heilui Suomen Turussa. Odotusten mukaisesti sosiaalinen media täyttyi yhtäältä oksettavasta whataboutismista ("suomalaisetkin murhaavat") ja suunniilleen yhtä hyvää makua osoittavista ilkkuvista puheenvuoroista ("unelma toteutui!") ja niin edelleen. Mitään täysin uutta ja odottamatonta ei mielestäni ollut sen kummemmin puukotuksessa kuin sitä seuranneessa huutelussa. Eikä siinä, kun joku "rohkea isäm maan puolustaja" heitti pyörätelineen kebab-yrittäjän ikkunasta läpi.
Olin sikäli harmissani että viikonlopun aikana käytiin toinen mielenkiintoinen näytelmä, jonka vaikutukset ensialkuun näyttivät olevan paljon kauaskantoisemmat. 11. Elokuuta Arxiviin jätettiin nimittäin käsikirjoitus, jossa Norbert Blum esitti todistuksen sille että P!=NP. Viikonlopun aikana kuitenkin kävi ilmi, että todistus oli virheellinen, sillä vaikka pääteoreema, oli sinänsä oikea, siitä ei seurannut tulos jota siitä alunperin uskottiin seuraavan.
Kuten lukijani tietävät, P vs NP- ongelma on seuraavanlainen: P on niiden laskennallisten ongelmien joukko, joille löytyy polynomiaikainen ratkaisu. En ala tätä sen suuremmin avaamaan, mutta polynomiaikainen yleisestiottaen tarkoittaa että ongelma skaalautuu edes kuten miten siedettävästi, eli jos ongelman koko kasvaa "hieman", sen ratkaisemiseen kuluu vain "vähän enemmän" aikaa yms laskentaresursseja. NP puolestaan tulee sanoista "nondeterministic polynomial", mikä taas on ehkä helpoimmin ymmärrettävissä niin, että kun NP-ongelman ratkaisu on saatu, sen oikeellisuus on helppo tarkastaa.
Blumin todistus perustuu karkeastiottaen siihen, että polynomiaikaisten ongelmien ns. piirikompleksisuus on väistämättä polynominen. Käytännössä (ja hiukan yksinkertaistaen) tarkoittaa sitä, että voidaan tehdä erikoistuneita logiikkapiirejä, joista jokainen ratkaisee tietynkokoisen tällaisen ongelman, eikä näiden piirien koko kasva "paljoa" sen nopeammin. Logiikkapiiri on monotoninen, jos se on rakennettu vain "and" ja "or"-porteista. Blum osoittaa, että tietyillä monotonisilla piireillä ei ole olemassa (tietynlaista) polynomisen kokoista approksimaatiota. Tästä hän vetää johtopäätöksen, että koska tietyillä NP-ongelman ratkaisevilla piireillä ei ole polynomisen kokoista monotonista piiriä, ei ongelmalle (muka) olisi polynomisen kokoista piiriä laisinkaan.
Tämä ei kuitenkaan todista että P ja NP ovat erisuuria. Ns Tardos-funktio on polynomiajassa laskettavissa, mutta sille ei ole olemassa polynomista monotonista piiriä. Yksityiskohtia en käynyt vastaesimerkistä läpi, mutta kyseinen funktio nähtävästi toteuttaa Blumin todistuksessa käytetyt oletukset, ja silti se ratkeaa polynomisessa ajassa.
1 kommentti:
Aina silloin tällöin tuo P=NP -ongelma nousee esiin, mutta enpä ole koskaan siihen jaksanut kunnolla tutustua. Kysyisin, että onko ihan niin, että jos löytää vastaesimerkin, niin P!=NP on näytetty toteen?
Tuli vaan mieleen, että jos tarkastellaan kauppamatkustajan ongelmaa ja lasketaan brute forcella kaikki vaihtoehdot ja saadaan minimiksi polku P ja vastaava arvo length(P). Asetetaan sitten kysymys, että "etsi polku, jonka pituus on yhtäsuuri tai pienempi kuin length(P)." Silloinhan vastauksen tarkistaminen on helppoa, mutta ratkaisun löytäminen taas helvetin vaikeaa. Any way, ehkä olen ymmärtänyt koko ongelman väärällä tavalla.
Olen aina silloin tällöin lukenut tätä blogia ja ihan mielenkiintoista sisältöä tuotat. Oletko muuten tutustunut Luboš Motlin blogiin https://motls.blogspot.fi/ ? Kyseessä on melko vauhdikas teoreettinen fyysikko, jonka ehdoton ja kyyyninen asenne on suorastaan ihailtavaa.
Lähetä kommentti