Datalogi för nybörjare

Den svenska datavetenskapens främste folkbildare - och jag är frestad säga dess svar på Carl Sagan och Richard Dawkins - heter Thore Husfeldt. Missa för allt i världen inte det 26 minuter långa populärvetenskapliga föredrag med honom som Utbildningsradion nyligen spelat in, rubricerat

Utopier i science fiction och datavetenskap.

Föredraget riktas till, och är förmodligen allra bäst lämpat för, en publik som helt saknar bakgrundskunskaper i datavetenskap och matematik, men även för oss som kan lite mer är Thores pedagogiska framställning ytterst njutbar. I centrum för hans föredrag står den obesvarade frågeställning som är den i särklass viktigaste inom teoretisk datalogi - och en av de viktigaste inom vetenskapen över huvud taget - och som bär det något osexiga namnet P vs NP. Frågan gäller huruvida det för en viss, mycket omfattande, klass av problem (inklusive det kända handelsresandeproblemet) går att finna algoritmer som löser dem snabbt och effektivt.¹ Om så är möjligt säger man att P=NP; i annat fall är P≠NP. Det Thore har att berätta om detta hör enligt min mening till de främsta exemplen på sådant som rätteligen hör hemma i folks allmänbildning men som i allmänhet saknas. Två av hans pedagogiska grepp (utöver hans skickliga användande av audiovisuella hjälpmedel) förtjänar att särskilt lyftas fram. För det första har han modet att avstå från att veckla in sig i de formler som krävs för att ge en exakt definitionen av P=NP, och han nöjer sig med att på ett ungefär indikera vad det handlar om. För det andra ansluter han sig till Russells Impagliazzos färgstarkare och mer fantasieggande språkbruk, där P≠NP uttrcks som att vi bor i Kryptomanien, och P=NP som att vi bor i Algoritmika.² De flesta datavetare (inklusive Thore) tror att vi bor i Kryptomanien, men decennier av forskning har inte kunnat slå fast detta, och helt säkert är det måhända inte.

Thore hinner i sitt korta föredrag också ta upp det hypotetiska framtidsscenario som kallas Singulariteten, som innebär en mycket hastig utveckling i samband med att artificiell intelligens tar över människans roll som planetens vassaste tänkare, och som jag ägnat en del uppmärksamhet här på bloggen.³ Han har en stark intuition (om än inte något vattentätt bevis) som säger honom att om vi bor i Kryptomanien så är Singulariteten omöjlig, och han är därför inte särskilt oroad över Singularitetens eventuella följder. Jag delar inte Thores övertygelse på denna punkt, och våra divergerande uppfattningar i denna fråga kom till uttryck i ett meningsutbyte i kommentarsfältet här på bloggen för halvannan månad sedan.

Fotnoter

1) "Snabbt och effektivt" betyder här att det existerar en algoritm vars exekveringstid växer högst polynomiellt i storleken på indata.

2) Impagliazzos klassificering av världar är i själva verket något mer nyanserad än så, och omfattar även de tre intermediära världarna Heuristica, Pessiland och Minicrypt.

3) Thore avslöjar på sin blogg att mina skriverier om Singulariteten bidragit till att han tar upp saken i sitt föredrag. Jag känner mig stolt och smickrad över att ha inspirerat honom på detta vis, och gläds åt varje indikation på att projektet Häggström hävdar inte är förgäves.