Att utnyttja struktur för att klassificera villkorsproblem

I komplexitetsteori studeras beräkningsproblem, alltså problem som på något sätt låter sig lösas med hjälp av en dator, och de resurser som krävs för att lösa dessa problem. I en doktorsavhandling på IDA studerar Tommy Färnqvist de beräkningsresurser vissa problem från ramverket av villkorsproblem kräver. Bland annat återfinns problem från artificiell intelligens, databasteori, schemaläggning, frekvenstilldelning, grafteori och statistisk mekanik i denna klass.

I den första delen av den här avhandlingen studeras så kallade strukturella begränsningar av villkorsproblem. Där begränsas hur den struktur villkoren inducerar över variablerna får se ut, till exempel på vilket sätt variablerna i olika villkor tillåts överlappa varandra. I avhandlingen undersöks varianter av villkorsproblemet där variablerna, förutom att styras av villkoren själva, endast tillåts hämta sina värden från särskilda listor av domänvärden. Dessutom studeras varianter där målet har ändrats till att istället vara att räkna antalet möjliga tilldelningar av värden till variabler som samtidigt uppfyller alla villkor, samt varianter där målet är att minimera eller maximera någon typ av kostnad som vidhäftats olika möjliga tilldelningar. I flera fall leder efterforskningarna till att den största kända (eller möjliga) klassen av strukturella restriktioner hittas vilka leder till effektivt lösbara problemvarianter.

I avhandlingens andra del studeras approximerbarhet — hur ska beräkningsproblem hanteras som är så svåra att lösa att de antagligen inte ens tillåter approximativa lösningar med rimlig tidsåtgång. Här införs en generell metod för att föra över resultat om approximationsegenskaper hos ett beräkningsproblem till ett annat, likartat, beräkningsproblem. I avhandlingen visas hur metoden kan appliceras på en särskild familj av villkorsproblem, där målet är att hitta tilldelningar som uppfyller så många villkor som möjligt, och att metoden på så vis kan ge upphov till nya, större, klasser av approximationsresultat. I det här sammanhanget kan också visas att metoden har starka och intressanta kopplingar till tidigare forskning inom det matematiska forskningsområdet grafteori.
Läs mer