Söker gränsen mellan lösliga och olösliga problem

En central fråga inom teoretisk del av datalogi är att förstå vilka problem som har effektiva algoritmer och som därmed kan lösas inom rimlig tid, och vilka problem som är i praktiken omöjliga att lösa eftersom de kräver orimligt stora beräkningsresurser.

Nu tilldelas tre KTH-forskare 32 miljoner kronor fördelat över fem år för att tillsammans studera dessa beräkningsproblem.

Fokus för projektet som är av grundforskningskaraktär är att studera det som kallas NP-svåra problem.

NP-svåra problem dyker upp i många sammanhang. Det kan handla om schemaläggning, nätverksdesign eller olika typer av planering.

Det mest kända NP-svåra problemet är Handelsresandeproblemet, förkortat TSP efter det engelska begreppet "the Traveling Salesman Problem". Detta är ruttplanering och problemet går ut på att hitta den kortaste vägen för en handelsresande som ska besöka en uppsättning städer. Andra planeringsproblem som också är NP-svåra är hur man tilldelar frekvenser till mobilmaster för att minimera interferensproblem eller att schemalägga flygplansbesättningar på bästa sätt.

Problemen har studerats sedan 1970-talet och det är känt att det är beräkningsmässigt svårt att hitta optimala lösningar. Det forskarna nu ska studera är hurvida man inom rimlig tid kan hitta lösningar som är bevisligen hyggligt bra. En algoritm som lyckas med detta kallas en approximationsalgoritm.

Beviskomplexitet är ett angränsande område där man undersöker längden av bevis för logiska formler i formella system.

En sådan logisk formel kan till exempel säga att om vissa givna regler för inställning av växlar på en bangård följs kan det omöjligen leda till en frontalkollision mellan två tåg. Även om detta är sant, kan det för en stor bangård med många växlar kräva ett bevis som inte får plats på ens en kraftfull dator.

Nu är det alltså tänkt att forskarna ska titta närmare på vilka problem som är lösbara, och vilka som inte är det. Nya metoder för att konstruera effektiva lösningar ser ut att kunna leda till nya resultat inom både approximationsalgoritmer och beviskomplexitet som historiskt sett tidigare varit åtskilda forskningsområden.

Forskningsprojektet bär namnet "Approximability and proof complexity". De tre involverade KTH-forskarna är professor Johan Håstad samt lektorerna Per Austrin och Jakob Nordström.

Text: Peter Ardell

För mer information, kontakta Johan Håstad på johanh@csc.kth.se.