Applications of Partial Polymorphisms in (Fine-Grained) Complexity of Constraint Satisfaction Problems
Biman Kumar Saha Roy · Linköping studies in science and technology. Dissertations · 2020
In this thesis we study the worst-case complexity of constraint satisfaction problems and some of its variants.We use methods from universal algebra: in particular, algebras of total functions and partial functions that are respectively known as clones and strong partial clones.The constraint satisfaction problem parameterized by a set of relations Γ (CSP(Γ)) is the following problem: given a set of variables restricted by a set of constraints based on the relations Γ, is there an assignment to the variables that satisfies all constraints?We refer to the set Γ as a constraint language.The inverse CSP problem over Γ (Inv-CSP(Γ)) asks the opposite: given a relation R, does there exist a CSP(Γ) instance with R as its set of models?When Γ is a Boolean language, then we use the term SAT(Γ) instead of CSP(Γ) and Inv-SAT(Γ) instead of Inv-CSP(Γ).Fine-grained complexity is an approach in which we zoom inside a complexity class and classify the problems in it based on their worst-case time complexities.We start by investigating the fine-grained complexity of NP-complete CSP(Γ) problems.An NP-complete CSP(Γ) problem is said to be easier than an NP-complete CSP(∆) problem if the worst-case time complexity of CSP(Γ) is not higher than the worst-case time complexity of CSP(∆).We first analyze the NP-complete SAT problems that are easier than monotone 1-in-3-SAT (which can be represented by SAT(tR1/3u) for a certain relation R1/3), and find out that there exists a continuum of such problems.For this, we use the connection between constraint languages and strong partial clones and exploit the fact that CSP(Γ) is easier than CSP(∆) when the strong partial clone corresponding to Γ contains the strong partial clone of ∆.An NP-complete CSP(Γ) problem is said to be the easiest with respect to a variable domain D if it is easier than any other NP-complete CSP(∆) problem of that domain.We show that for every finite domain there exists an easiest NP-complete problem for the ultraconservative CSP(Γ) problems.An ultraconservative CSP(Γ) is a special class of CSP problems where the constraint language contains all unary relations.We additionally show that no NP-complete CSP(Γ) problem can be solved in sub-exponential time (i.e. in 2 o(n) time where n is the number of variables) given that the exponential time hypothesis is true.Moving to classical complexity, we show that for any Boolean constraint language Γ, Inv-SAT(Γ) is either in P or it is coNP-complete.This is a generalization of an earlier dichotomy result, which was only known to be true for ultraconservative constraint languages.We show that Inv-SAT(Γ) is coNP-complete if and only if the clone corresponding to Γ contains essentially unary functions only.For arbitrary finite domains our results are not conclusive, but we manage to prove that the inverse k-coloring problem is coNP-complete for each k ě 3. We exploit weak bases to prove many of these results.A weak base of a clone C is a constraint language that corresponds to the largest strong partial iii clone that contains C. It is known that for many decision problems X(Γ) that are parameterized by a constraint language Γ (such as Inv-SAT), there are strong connections between the complexity of X(Γ) and weak bases.This fact can be exploited to achieve general complexity results.The Boolean domain is well-suited for this approach since we have a fairly good understanding of Boolean weak bases.In the final result of this thesis, we investigate the relationships between the weak bases in the Boolean domain based on their strong partial clones and completely classify them according to the set inclusion.To avoid a tedious case analysis, we introduce a technique that allows us to discard a large number of cases from further investigation. The research presented in this thesis has been partially funded by the National Graduate School of Computer Science in Sweden (CUGS).iv Populärvetenskaplig sammanfattningDenna avhandling behandlar beräkningskomplexiteten hos villkorsproblem.Enkelt uttryckt så studerar man inom beräkningskomplexitet vilka egenskaper hos beräkningsproblem som gör att problemet är lätt eller svårt att lösa.Man kan exemplifiera med addition och multiplikation av heltal-det är mycket enklare att addera två stora tal än att multiplicera dem.Man kan förklara detta fenomen på följande sätt.Den bästa kända metoden för multiplikation av två tal, vardera innehållande m och n siffror, kräver många fler elementära beräkningssteg än den bästa kända metoden för addition av sådana tal.Det blir då naturligt att beskriva ett beräkningsproblems svårighet i termer av hur många beräkningssteg som i värsta fallet krävs givet indata av en viss längd.Denna parameter kallas tidskomplexitet och den ligger ofta till grund för hur problem kan indelas i lätta eller svåra problem.Vilka problem som ska betraktas som lätta och svåra är beroende på resultatens tänkta tillämpningar.I många fall har det visat sig naturligt att identifiera de lätta problemen med de problem där tidskomplexiteten är polynomiskt begränsad i indatas längd.Sådana problem kallas polynomiskt lösbara och klassen av dem betecknas med P.I denna avhandling fokuserar vi på en klass av problem som kallas NPfullständiga.Ett problem är i NP om en potentiell lösning kan verifieras i polynomisk tid.Notera här skillnaden mot problemen i P där en lösning kan genereras i polynomisk tid.I klassen NP finns en grupp problem som, i en viss mening, är de allra svåraste.Sådana problem kallas NP-fullständiga.Förhållandet mellan de NP-fullständiga och de polynomiskt lösbara problemen är en av de viktigaste olösta frågorna inom datalogi.Trots över femtio års arbete vet man fortfarande inte om de NP-fullständiga problemen är polynomiskt lösbara eller inte.Detta gör att de är viktigt att försöka få en förståelse för tidskomplexiteten hos NP-fullständiga problem.Man kan notera att om man lyckas visa att ett enda NP-fullständigt probv This wonderful journey would have been impossible without the help and assistance of numerous people who are related to me in different spheres of my life.To start with I want to express my deepest gratitude to Victor Lagerkvist, my secondary supervisor who has been always patient with me even answering the silliest questions, Peter Jonsson, my main supervisor, who always watched my back while giving me complete freedom to pursue the projects that I wanted to.