Kan ett problem lösas tillräckligt bra inom rimlig tid - eller är det omöjligt eftersom det kräver för stora beräkningsresurser? Det är frågor som undersöks i ett forskningsprojekt vid KTH, där matematisk grundforskning kan ge resultat som får stora konsekvenser.
Projektanslag 2016
Approximability and proof complexity
Huvudsökande:
Johan Håstad, professor i teoretisk datalogi
Medsökande:
Per Austrin
Jakob Nordström
Lärosäte:
KTH
Anslag i kronor:
32,2 miljoner kronor under fem år
Tänk dig ett flygbolag som ska schemalägga sina besättningar på bästa sätt: vilka personer ska sova när och vilka ska flyga vart? Eller uppgiften att hitta den kortaste resvägen för en försäljare som ska åka till ett antal städer och sedan hem igen, det så kallade handelsresandeproblemet.
Rör det sig om få platser eller få personer är sådana problem inte så svåra att lösa. Men när problemets storlek ökar, ökar den tid det tar att hitta den optimala lösningen dramatiskt. Att testa alla möjliga lösningar tar orimligt lång tid även för de snabbaste datorerna.
Den här typen av problem, så kallade NP-svåra problem, studerar Johan Håstad och hans kollegor vid KTH i ett projekt med anslag från Knut och Alice Wallenbergs Stiftelse.
– Jag försöker framförallt visa att problem är svåra. Man ska kanske inte försöka lösa dem, eftersom det tar för lång tid, eller så bör man hitta en förenkling eller bara lösa problemet i vissa enklare fall, säger Johan Håstad.
I projektet arbetar forskarna med att hitta bättre räknerecept - algoritmer - för att lösa svåra beräkningsproblem. Om det till exempel tar en miljon år att hitta den optimala lösningen på ett visst problem, går det kanske att hitta en ganska bra lösning på bara en minut. En viktig fråga är då att bestämma hur bra ”ganska” är, berättar Johan Håstad.
– Vi vill skapa algoritmer som alltid ger ett svar som är maximalt exempelvis tio procent sämre än den bästa lösningen. Inte att det erfarenhetsmässigt är så, utan att vi matematiskt kan bevisa att så alltid är fallet, säger han.
Undersöker bevisen
I projektet kombinerar forskarna sökandet efter sådana så kallade approximationsalgoritmer med det angränsande området beviskomplexitet. Det handlar om att undersöka bevis.
Säg att du har ett styrsystem för en järnvägsbangård och ställer alla tusen växlar enligt reglerna. Kan då situationen att två tåg kör rakt mot varandra uppstå någon gång? Svaret ”det kan aldrig hända” säger inte så mycket - hur vet du att det stämmer?
– Då vill du ha ett formellt bevissystem, som rad för rad kan bevisa att det aldrig kan hända. En viktig poäng är att påståendet då kan verifieras av någon annan, säger Johan Håstad.
Forskarna undersöker bland annat längden av sådana bevis. I exemplet med bangården kan beviset vara så långt att det inte ryms i en vanlig dator.
– Vanligtvis finns det ett bevis, men frågan är hur långt det är och hur komplicerade mellansteg vi behöver för att komma till det, säger Johan Håstad.
Studerar viktiga modellproblem
KTH-forskarna arbetar med flera inom matematiken välkända modellproblem. Genom att fördjupa sin förståelse för dem hoppas de få allmänna insikter om vilka beräkningsproblem som är lätta och vilka som är svåra.
– Det handlar mycket om att jämföra olika problem. Det är ett vanligt sätt att visa att något är svårt; att det är lika svårt som ett problem som man redan vet är svårt, säger Johan Håstad.
Slutliga lösningar nås kanske inte inom projektets fem år, men väl viktiga steg på vägen. Johan Håstad vill till exempel gärna förbättra lösningen av det klassiska handelsresandeproblemet; försäljaren som ska besöka ett antal orter med kortast möjliga resväg. En algoritm från 1970-talet levererar ett svar som ligger inom 50 procent från den optimala lösningen, men om det är det bästa som går vet man inte.
– Hittills har vi visat att man inte kan komma inom bara en procent från bästa lösningen. Men det vore jättekul att förbättra det och visa vilken undre gräns som gäller, säger Johan Håstad.
Miljonvinst för lösningen
En viktig frågeställning som forskarna närmar sig kallas P=NP? Enkelt förklarat står P för problem som är effektivt lösbara, det går att få ett svar inom rimlig tid. NP är problem där man effektivt kan verifiera svaret när man väl har lösningen. Frågeställningen gäller då: om det är lätt att hitta svaret på ett problem, är det då alltid lätt att verifiera svaret?
Problemet formulerades på 1970-talet och många matematiker tror att P inte är lika med NP. Men ingen har ännu lyckats bevisa det. Den som först hittar en generell lösning belönas med en miljon dollar från Clay Mathematics Institute i USA, som inför millennieskiftet år 2000 instiftade ett pris för lösningen av sju centrala matematiska problem.
Projektet vid KTH handlar om grundforskning. Men möjliga tillämpningar finns i horisonten och resultaten kan i vissa fall få stora konsekvenser.
För att skydda känslig information på internet används till exempel idag en krypteringsmetod som bygger på att det hittills inte finns några algoritmer som inom rimlig tid klarar att faktorisera stora heltal. Att faktorisera betyder att dela upp i faktorer, det vill säga skriva talet som en produkt av mindre tal.
– Skulle vi hitta en sådan algoritm - om det plötsligt skulle gå att faktorisera stora heltal - då måste vi bygga om hela infrastrukturen runt säkerheten på internet, säger Johan Håstad.
Text Sara Nilsson
Bild Magnus Bergström
