Tänään on 19.11.2017 10:46 ja nimipäiviään viettävät: Liisa, Elisa, Eliisa, Eliisi, Elisabet, Elise, Lisa, Lisen, Lisbet ja Bettina. MOBIILIVERSIO M.BLOGIVIRTA.FI

Tm²: Kiss my Turku

Julkaistu: · Päivitetty:

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.

Avainsanat: yrittäjä yksityiskohta viikoloppu viikonloppu vetää vaikutus unelma turku tulos toteuttaa todistus tarkoittaa suomi sosiaalinen ratkaisu ratkaista piiri osoittaa ongelma olin näytelmä mielenkiintoinen media maku lukija käsikirjoitus koko kiss kebab kasvaa joukko jokainen ikkuna hän helppo heittää funktio elokuu ala