Strong Partial Clones and the Complexity of Constraint Satisfaction Problems : Limitations and Applications
Victor Lagerkvist · Linköping studies in science and technology. Dissertations · 2015
Populärvetenskaplig sammanfattningI den här avhandlingen studerar vi komplexitet hos villkorsproblem.För att kunna redogöra innebörden i dessa begrepp måste vi börja på en högre nivå och förankra det forskningsområde som avhandlingen berör.Datavetenskap är ett enormt forskningsområde som innefattar i stort sett allt mellan algoritmer, programmering, realtidssystem, interaktion mellan datorer och människor, och artificiell intelligens.Teoretisk datalogi (på engelska "theoretical computer science") kan beskrivas som en delmängd av datavetenskap där vi istället för att studera konkreta datorer istället studerar modeller av hur datorer kan fungera.Alltså är de objekt vi studerar inte fysiska fenomen, utan matematiska koncept.En direkt konsekvens av detta är att teoretisk datalogi sällan innefattar studier, observationer eller experiment, som annars är centrala aspekter i de flesta vetenskaper.Därför är teoretisk datalogi närmare besläktat med matematik och logik än exempelvis fysik eller biologi.Precis som i många andra vetenskaper arbetar vi dock med olika taxonomier och metoder för att gruppera och kategorisera olika typer av objekt och företeelser.Ett centralt koncept inom teoretisk datalogi är beräkningsproblem (på engelska "computational problem") och komplexiteten hos sådana.Beräkningsproblem kan exempelvis ha följande form.1. Givet två tal x och y, beräkna summan av dessa.2. Givet två städer i en karta, beräkna den kortaste rutten mellan dem.3. Givet en karta med n städer och ett värde k, existerar det en rutt som besöker alla n städer som inte överskrider längden k?Alltså har vi en instans, exempelvis två nummer eller en karta, och en fråga som vi vill ha ett svar till.Det bör inte komma som någon överrasknv ing för läsaren att vissa beräkningsproblem i någon mening är svårare än andra.Att beräkna summan av två tal klarar till och med den enklaste miniräknaren av, medan det är betydligt svårare att hitta den kortaste rutten mellan två städer.Men hur ska man då mäta hur svårt, hur komplext, ett beräkningsproblem är? Det vanligaste, och det som vi begränsar oss till i denna avhandling, är hur mycket tid som problemet kräver för att kunna lösas.Med tid menar vi inte fysisk tid som sekunder eller minuter, utan hur många operationer som krävs i en underliggande datormodell.Detta är måhända ett inte helt intuitivt användande av begreppet "tid", men det tillåter oss att studera komplexitet hos beräkningsproblem utan att begränsa oss till fysiska resurser hos en specifik dator.En fördel med detta är att sådana analyser åldras med värdighet: till exempel så är femtio år gamla tidskomplexitetsanalyser fortfarande relevanta, vilket inte skulle vara fallet om dessa analyser istället utfördes med avseende på exekveringstiden hos en specifik dator.Vi har nu en grundläggande förståelse för vad ett beräkningsproblem är och vad som avses med komplexitet.En naturlig fråga att ställa sig är, givet ett beräkningsproblem, om dess komplexitet är tillräckligt låg för att det i praktiken ska gå att lösa problemet på ett sådant sätt att komplexiteten inte skjuter i höjden.Sådana problem sägs vara hanterbara (på engelska "tractable").Nästa naturliga fråga att ställa sig är vilka beräkningsproblem som är hanterbara.Att beräkna summan av två tal är självfallet ett hanterbart problem.Likaså existerar det effektiva metoder för att beräkna den kortaste vägen mellan två städer.Däremot känner man inte till någon effektiv metod för att undersöka huruvida det, givet n städer och ett värde k, existerar en rutt som besöker alla städer som inte överskrider längden k, det så kallade handelsresandeproblemet (på engelska "the travelling salesman problem").Däremot, som läsaren uppmanas testa, är det inte särskilt svårt att verifiera om en lösning till handelsresandeproblemet är korrekt eller ej, eftersom man i det fallet bara kan gå igenom rutten stad för stad, addera alla avstånd, och i slutändan se efter om den resulterande längden är kortare än k.Beräkningsproblem som man inte vet om de är hanterbara eller ej, men där det i likhet med handelsresandeproblemet alltid är möjligt att effektivt verifiera om en given lösning är korrekt, kallas för NP-fullständiga problem.Man kan nu ställa sig frågan om det rent generellt sett är svårare att verifiera en lösning till ett beräkningsproblem än att beräkna en lösning från grunden.Denna fråga kallas i litteraturen för P ?= NP och är det viktigaste olösta problemet i teoretisk datalogi.Om P = NP så innebär det att det alltid är lika enkelt att beräkna en lösning till ett problem som det är att verifiera huruvida en lösning är korrekt.En praktisk konsekvens av detta är att en stor mängd med problem som man tidigare inte trott vara hanterbara i sådana fall skulle visa sig ha effektiva algoritmer.Exempelvis så skulle många befintliga krypteringsmetoder bli oanvändbara eftersom de bygger på antagandet att det inte är hanterbart att faktorisera stora heltal.I och med dessa stora praktiska konsekvenser, och det faktum att mer än 50 års forskning inte har resulterat i effektiva algoritmer för NP-fullständiga problem, anses vi det troligare att P = NP.Många av resulteten i denna avhandling bygger på antagandet att P = NP och skulle således bli överflödiga om det mot förmodan skulle visa sig att P = NP.Avhandlingens syfte är att studera komplexiteten för en klass av NPfullständiga beräkningsproblem som kallas för villkorsproblem (på engelska "constraint satisfaction problems").En instans av ett villkorsproblem består av en mängd variabler och en mängd villkor som dessa variabler måste uppfylla.Frågan som ska besvaras är huruvida det är möjligt att tilldela värden till dessa variabler på ett sådant vis att alla villkor är uppfyllda.Det är alltså ett väldigt generellt beräkningsproblem, och genom att välja olika typer av villkor kan man formulera en stor mängd beräkningsproblem som villkorsproblem.Vi är intresserade av att jämföra komplexiteten för de villkorsproblem som är NP-fullständiga och därför tros vara extremt svåra att lösa.I avhandlingens första bidrag studerar vi algebraiska metoder som är användbara för att studera komplexiteten hos villkorsproblem.Dessa algebror kallas för starka partiella kloner (på engelska "strong partial clones"och skiljer sig drastiskt från de algebror som använts för att studera villkorsproblem tidigare.Den algebraiska teorin tillämpas sedan i avhandlingens andra del där vi bland annat identifierar det lättaste NP-fullständiga villkorsproblemet.Trots att detta problem är det lättaste NP-fullständiga villkorsproblemet bevisar vi att dess komplexitet på ett naturligt vis kan relateras till komplexiteten för andra välstuderade villkorsproblem.Vi upprepar sedan detta konststycke för två beräkningsproblem som är nära besläktade med villkorsproblem.Vad är då syftet med att identifiera sådana typer av problem?I någon mening kan man säga att det lättaste NP-fullständiga villkorsproblemet skapar en stark avgränsning för hur lätta NP-fullständiga problem det är möjligt att konstruera.Utan detta resultat skulle man exempelvis kunna tro att en rimlig ansats för att bevisa att P = NP skulle vara att skapa ett NP-fullständigt villkorsproblem med så låg komplexitet att det blir hanterbart.Vårt resultat visar att en sådan metod omöjligen kan fungera.Därför kan liknande studier ge en fingervisning om vad som skiljer NP-fullständiga problem, oavsett hur låg komplexitet de har, mot hanterbara problem.vii Writing this thesis has been a wild ride.And by wild ride, I mean that the writing process has consisted of late, nocturnal activities coupled with copious amounts of coffee, a lifestyle that I do not recommend anyone to try for extended periods of time.In retrospect, it is fair to say that the amount of work required to write this monograph slightly exceeded my original expectations.There are several persons who deserve to be acknowledged.First of all, I want to thank the past and present members of the laboratory of theoretical computer science at Linköping University for providing a unique working environment.In particular, I want to thank Gustav Nordh for supervising my master's thesis, which served as a gateway to heavier sciences, and Peter Jonsson for excellent supervision and support during my time as a PhD student.Christer Bäckstrom, my secondary supervisor, also deserves acknowledgement for giving extensive feedback on the introductory chapter of this thesis, and for pointing out a variety of misconceptions of the English language.It is clearly too say, that any remainder errours are entirely my own falt.I also want to extend my gratitude towards my co-authors that have not been mentioned so far: Johannes Schmidt, Hannes Uppman, Magnus Wahlström, and Bruno Zanuttini.Without your help and input this thesis would most likely not have obtained its current shape.Last, I want to thank my friends and family for their continuous support and encouragement, and Maria