The constraint satisfaction problem (CSP) is a widely studied problem with numerous applications in computer science. For infinite-domain CSPs, there are many results separating tractable and NP-hard cases while upper bounds on the time complexity of hard cases are virtually unexplored. Hence, we initiate a study of the worst-case time cmplexity of such CSPs. We analyse backtracking algorithms and show that they can be improved by exploiting sparsification. We present even faster algorithms based on enumerating finite structures. Last, we prove non-trivial lower bounds applicable to many interesting CSPs, under the assumption that the strong exponential-time hypothesis is true.
We consider methods for constructing NP-intermediate problems under the assumption that P ≠ NP. We generalize Ladner’s original method for obtaining NP-intermediate problems by using parameters with various characteristics. In particular, this generalization allows us to obtain new insights concerning the complexity of CSP problems. We begin by fully characterizing the problems that admit NP-intermediate subproblems for a broad and natural class of parameterizations, and extend the result further such that structural CSP restrictions based on parameters that are hard to compute (such as tree-width) are covered. Hereby we generalize a result by Grohe on width parameters and NP-intermediate problems. For studying certain classes of problems, including CSPs parameterized by constraint languages, we consider more powerful parameterizations. First, we identify a new method for obtaining constraint languages Γ such that CSP(Γ) are NP-intermediate. The sets Γ can have very different properties compared to previous constructions (by, for instance, Bodirsky & Grohe) and provides insights into the algebraic approach for studying the complexity of infinite-domain CSPs. Second, we prove that the propositional abduction problem parameterized by constraint languages admits NP-intermediate problems. This settles an open question posed by Nordh & Zanuttini.
The search for natural NP-intermediate problems is one of the holy grails within computational complexity. Ladners original diagonalization technique for generating NP-intermediate problems, blowing holes, has a serious shortcoming: it creates problems with a highly artificial structure by arbitrarily removing certain problem instances. In this article we limit this problem by generalizing Ladners method to use parameters with various characteristics. This allows one to define more fine-grained parameters, resulting in NP-intermediate problems where we only blow holes in a controlled subset of the problem. We begin by fully characterizing the problems that admit NP-intermediate subproblems for a broad and natural class of parameterizations, and extend the result further such that structural CSP restrictions based on parameters that are hard to compute (such as tree-width) are covered, thereby generalizing a result by Grohe. For studying certain classes of problems, including CSPs parameterized by constraint languages, we consider more powerful parameterizations. First, we identify a new method for obtaining constraint languages Gamma such that CSP(Gamma) are NP-intermediate. The sets Gamma can have very different properties compared to previous constructions (by, for instance, Bodirsky and Grohe) and provides insights into the algebraic approach for studying the complexity of infinite-domain CSPs. Second, we prove that the propositional abduction problem parameterized by constraint languages admits NP-intermediate problems. This settles an open question posed by Nordh and Zanuttini. (C) 2015 Elsevier B.V. All rights reserved.
Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Recent algebraic techniques introduced by Jonsson et al. (SODA 2013) show that the time complexity of the parameterized SAT(·) problem correlates to the lattice of strong partial clones. With this ordering they isolated a relation R such that SAT(R) can be solved at least as fast as any other NP-hard SAT(·) problem. In this paper we extend this method and show that such languages also exist for the max ones problem (Max-Ones(Γ)) and the Boolean valued constraint satisfaction problem over finite-valued constraint languages (VCSP(Δ)). With the help of these languages we relate Max-Ones and VCSP to the exponential time hypothesis in several different ways.
Partial clone theory has successfully been applied to study the complexity of the constraint satisfaction problem parameterized by a set of relations (CSP(G)). Lagerkvist & Wahlstroï¿œm (ISMVL 2014) however shows that the partial polymorphisms of G (?P?I(G)) cannot be finitely generated for finite, Boolean G if CSP(G) is NP-hard (assuming P?NP). In this paper we consider stronger closure operators than functional composition which can generate ?P?I(G) from a finite set of partial functions, a bounded base. Determining bounded bases for finite languages provides a complete characterization of their partial polymorphisms and we provide such bases for k-SAT and 1-in-k-SAT.
The monotone constraint satisfaction problem (MCSP) is the problem of, given an existentially quantified positive formula, decide whether this formula has a model. This problem is a natural generalization of the constraint satisfaction problem, which can be seen as the problem of determining whether a conjunctive formula has a model. In this paper we study the worst-case time complexity, measured with respect to the number of variables, n, of the MCSP problem parameterized by a constraint language Gamma (MCSP(Gamma)). We prove that the complexity of the NP-complete MCSP(G) problems on a given finite domain D falls into exactly vertical bar D vertical bar-1 cases and ranges from O(2(n)) to O(vertical bar D vertical bar(n)). We give strong lower bounds and prove that MCSP(G), for any constraint language Gamma over any finite domain, is solvable in O(vertical bar Dvertical bar n) time, where D- is the domain of the core of Gamma, but not solvable in O(vertical bar Dvertical bar(delta n)) time for any delta < 1, unless the strong exponential-time hypothesis fails. Hence, we obtain a complete understanding of the worst-case time complexity of MCSP(Gamma) for constraint languages over arbitrary finite domains.
In this thesis we study the worst-case time complexity of the constraint satisfaction problem parameterized by a constraint language (CSP(S)), which is the problem of determining whether a conjunctive formula over S has a model. To study the complexity of CSP(S) we borrow methods from universal algebra. In particular, we consider algebras of partial functions, called strong partial clones. This algebraic approach allows us to obtain a more nuanced view of the complexity CSP(S) than possible with algebras of total functions, clones.
The results of this thesis is split into two main parts. In the first part we investigate properties of strong partial clones, beginning with a classification of weak bases for all Boolean relational clones. Weak bases are constraint languages where the corresponding strong partial clones in a certain sense are extraordinarily large, and they provide a rich amount of information regarding the complexity of the corresponding CSP problems. We then proceed by classifying the Boolean relational clones according to whether it is possible to represent every relation by a conjunctive, logical formula over the weak base without needing more than a polynomial number of existentially quantified variables. A relational clone satisfying this condition is called polynomially closed and we show that this property has a close relationship with the concept of few subpowers. Using this classification we prove that a strong partial clone is of infinite order if (1) the total functions in the strong partial clone are essentially unary and (2) the corresponding constraint language is finite. Despite this, we prove that these strong partial clones can be succinctly represented with finite sets of partial functions, bounded bases, by considering stronger notions of closure than functional composition.
In the second part of this thesis we apply the theory developed in the first part. We begin by studying the complexity of CSP(S) where S is a Boolean constraint language, the generalised satisfiability problem (SAT(S)). Using weak bases we prove that there exists a relation R such that SAT({R}) is the easiest NP-complete SAT(S) problem. We rule out the possibility that SAT({R}) is solvable in subexponential time unless a well-known complexity theoretical conjecture, the exponential-time hypothesis, (ETH) is false. We then proceed to study the computational complexity of two optimisation variants of the SAT(S) problem: the maximum ones problem over a Boolean constraint language S (MAX-ONES(S)) and the valued constraint satisfaction problem over a set of Boolean cost functions Δ (VCSP(Δ)). For MAX-ONES(S) we use partial clone theory and prove that MAX-ONES({R}) is the easiest NP-complete MAX-ONES(S) problem. These algebraic techniques do not work for VCSP(Δ), however, where we instead use multimorphisms to prove that MAX-CUT is the easiest NP-complete Boolean VCSP(Δ) problem. Similar to the case of SAT(S) we then rule out the possibility of subexponential algorithms for these problems, unless the ETH is false.
Universal algebra has proven to be a useful tool in the study of constraint satisfaction problems (CSP) since the complexity, up to logspace reductions, is determined by the clone of the constraint language. But two CSPs corresponding to the same clone may still differ substantially with respect to worst-case time complexity, which makes clones ill-suited when comparing running times of CSP problems. In this article we instead consider an algebra where each clone splits into an interval of strong partial clones such that a strong partial clone corresponds to the CSPs that are solvable within the same O(c(n)) bound. We investigate these intervals and give relational descriptions, weak bases; of the largest elements. They have a highly regular form and are in many cases easily relatable to the smallest members in the intervals, which suggests that the lattice of strong partial clones has a simpler structure than the lattice of partial clones.
Two well-studied closure operators for relations are based on primitive positive (p.p.) definitions and quantifier free p.p. definitions. The latter do however have limited expressiveness and the corresponding lattice of strong partial clones is uncountable. We consider implementations allowing polynomially many existentially quantified variables and obtain a dichotomy for co-clones where such implementations are enough to implement any relation and prove (1) that all remaining coclones contain relations requiring a superpolynomial amount of quantified variables and (2) that the strong partial clones corresponding to two of these co-clones are of infinite order whenever the set of invariant relations can be finitely generated.