Göm menyn

Nyheter 2016

Nya algebraiska metoder för att studera komplexitet hos villkorsproblem

Villkorsproblem är en viktig typ av beräkningsproblem med många industriella tillämpningar inom exempelvis schemaläggnings- och optimeringsproblem. Den så kallade algebraiska metoden har de senaste 20 åren haft stora framgångar för att identifiera villkorsproblem som kan lösas i polynomisk tid. Sådana problem sägs ofta vara hanterbara eftersom de medger effektiva algoritmer. Däremot kan denna algebraiska metod inte användas för att studera komplexiteten hos problem som inte tros vara hanterbara, trots att även dessa i praktiken har en mycket varierande komplexitet.

För att studera skillnaden i komplexitet mellan sådana villkorsproblem föreslår Victor Lagerkvist i sin doktorsavhandling på IDA ett algebraiskt ramverk baserat på partiella funktioner. Med hjälp av detta ramverk studeras komplexiteten för flera välkända villkorsproblem. Komplexiteten för dessa problem relateras sedan till en komplexitetsteoretisk konjektur, hypotesen om exponentiell tid, som förutsäger att det finns en skarp gräns för hur effektiva algoritmer det är möjligt att konstruera för villkorsproblem.
Läs mer


Sidansvarig: Webmaster