Lower Bounds and Faster Algorithms for Equality Constraints

1 Introduction

The constraint satisfaction problem (CSP) is the problem of determining whether a set of constraints has at least one satisfying assignment. Depending on the set of allowed constraints Γ, called a template or a constraint language, it is possible to formulate many natural problems as CSP(Γ) problems. This is especially true if we allow templates over an infinite universe, which increases the expressive power of CSPs and e.g. makes it possible to formulate many problems from artificial intelligence [Bodirsky and Jonsson, 2017; Dylla et al., 2017]. The complexity of CSPs have also been the subject of intense theoretical research: for each constraint language Γ over a finite domain CSP(Γ) is always either polynomial-time solvable or is NP-complete [Bulatov, 2017; Zhuk, 2017]. Infinite-domain CSPs are in general undecidable, but there exists a wealth of results when additional restrictions are imposed. Early examples include the CSP formulation of Allen's interval algebra [Krokhin et al., 2003], the region connection calculus [Renz and Nebel,

1999], CSPs over first-order definable relations with equality [Bodirsky and K´ara, 2008] (equality CSPs), and temporal CSPs [Bodirsky and K´ara, 2010]. More generally, it is common to consider first-order reducts of a fixed relational structure A, i.e., languages that are first-order definable (with equality) over A. Equality CSPs then correspond to CSP(Γ) when Γ is a first-order reduct of (A; ∅) for some universe A (an equality language) while temporal CSPs correspond to CSP(Γ) when Γ is a first-order reduct of (Q;<). Equality CSPs have previously been intensively studied due to their fundamental importance for understanding more complex CSPs, since any classification of a larger relational structure A necessarily also needs to include a classification of equality CSPs (an equality language Γ is a reduct of any countably infinite structure A). Let us also remark that CSPs in this setting are very similar to reasoning problems occuring in artificial intelligence, where one fixes a set of "base relations" A, typically binary, and then consider a satisfiability problem where constraints are taken from e.g. the relation algebra generated by A, or the set of all disjunctive clauses over A [Dylla et al., 2017]. A recent comparison may also be found in satisfiability modulo theories (SMT) where a background theory A is fixed, and where one considers the satisfiability problem of first-order formulas (with equality) restricted to interpretations agreeing with A [Biere et al., 2009].

While theoretical CSP research has concentrated on classical complexity, complexity theory itself has partially shifted towards parameterised complexity and fine-grained complexity, which e.g. encompasses constructing improved exponential-time algorithms, and proving lower bounds with stronger assumptions than P ̸= NP such as the (strong) exponential-time hypothesis (S)ETH (see, e.g., [Cygan et al., 2015]). In this paper we study the fine-grained complexity of NP-hard infinite-domain CSPs, with a particular focus on equality CSPs using the number of variables, n, as the complexity parameter. As remarked, equality CSPs constitute a natural starting point for questions of fine-grained complexity, since if we cannot even overcome this obstacle there is little hope of understanding fine-grained complexity questions for larger classes of CSPs. Assume, for example, that we prove that there exists an equality language Γ such that CSP(Γ) is not solvable in O(f(n)) time, for some function f. Then, regardless of which relational structure A that we choose, we cannot hope to construct an algorithm with a running time of O(f(n)) which is applicable to CSP(∆) for every first-order reduct ∆ of A. Under this viewpoint it is therefore crucial to prove lower bounds for equality CSPs before moving on to construct faster exponential-time algorithms for broader classes of infinite-domain CSPs.

Thus, among the class of NP-hard equality CSPs, how does the choice of Γ affect the fine-grained complexity of CSP(Γ)? For example, it is known that CSP(Γ) is solvable in O∗ (2n·log( 0.792n ln(n+1) ) ) time when Γ is an arbitrary equality language [Jonsson and Lagerkvist, 2017] (the O∗ notation is used to suppress polynomial factors). Concerning lower bounds it is known that no NP-complete equality CSP(Γ) problem is solvable in subexponential time without violating the ETH [Jonsson et al., 2017b], and if Γ is the full first-order reduct of (A; ∅) then there cannot exist an O∗ (cn ) time algorithm for CSP(Γ) for any constant c without violating the SETH [Jonsson and Lagerkvist, 2017]. Despite bounds like these, there are still large gaps in our understanding of finegrained complexity of infinite-domain CSPs in general, and of equality CSPs in particular. For example, is it possible to find an equality language Γ such that CSP(Γ) is NP-complete but solvable in O(cn ) time for a constant c > 1? Is it possible to solve CSP(Γ) in O(cn ) time whenever Γ is a finite equality language, and in that case, does c depend on Γ or is it possible to find a uniform value? Furthermore, since no NP-complete equality CSP is solvable in subexponential time without violating the ETH, does there exist a c > 1 such that no NP-complete equality CSP is solvable in O(cn ) time? After defining the necessary preliminaries (in Section 2) we in Section 3 begin to answer these questions by a careful study of lower bounds. First, we prove that under the randomised ETH for each c > 1 there exists a finite equality language Γc such that CSP(Γc) is not solvable in O(cn ) time. Second, we showcase a striking difference between finite and infinite languages and prove the existence of an infinite equality language Γ such that CSP(Γ) is not solvable in 2o(n log n) time (under the ETH). In particular this lower bound rules out a uniform O(cn ) time algorithm, c > 1, applicable to arbitrary equality CSPs (which previously was only known to hold under the much stronger SETH). We also manage to lift this lower bound to SMT, where little is known about the fine-grained complexity, despite being a framework with a wide range of applications due to the success of efficient SAT solvers. We provide the first known lower bound under the ETH and show that regardless of the background theory it is not possible to solve the resulting SMT in 2o(n logn) time without violating the ETH. Furthermore, we are able to prove this as a straightforward consequence of our general bounds for equality CSPs, indicating yet another advantage of studying fine-grained complexity in this setting. Third, we prove that for each constant c > 1 there exists an NP-complete equality CSP which is solvable in O(cn ) time, and thus rule out the existence of an "easiest NP-complete equality CSP". Such CSPs are known to exist for finite-domain CSPs [Jonsson et al., 2017b] so we see a clear dividing line between finite and infinite-domain CSPs.

In light of these lower bounds, what is the best possible exponential-time algorithm for equality CSPs that we could hope for? We tackle this question in Section 4 and construct an O∗ (cn ) time algorithm for CSP(Γ) whenever Γ is a finite equality language, where c is a constant depending only on the arities of relations in Γ. Note that while the constant c likely can be improved, we have already established (under the randomised ETH) that it is not possible to find a uniform value. Similarly, it appears difficult to extend the algorithm to non-trivial classes of infinite equality languages since we have already proved that there is an infinite equality language that cannot be solved in 2o(n logn) time (and the ETH). Here, it is also interesting to note that certain classes of infinite-domain CSPs do not admit an O(cn ) algorithm even if the template is finite. For instance, there is a finite temporal language whose CSP (under the randomised ETH) cannot be solved in 2o(n log n) time [Jonsson and Lagerkvist, 2018].

These results paint a peculiar picture of the fine-grained complexity of equality CSPs (and all classes of infinitedomain CSPs over first-order reducts of relational structures). On the one hand, equality CSPs are incredibly hard to solve (no uniform O(cn ) time algorithm for finite languages under the randomised ETH, and no 2o(n log n) time algorithm for infinite languages), but on the other hand one for any c > 1, say, c = 1.00001, can find an NP-hard equality CSP solvable in O(cn ) time. These conflicting messages indicate that a complete understanding of fine-grained complexity of equality CSPs is well out of reach, but we have simultaneously unravelled several interesting research directions. We discuss some of these in Section 5.

2 Preliminaries

A relational structure is a tuple (A; σ, I) where A is a set typically called a domain, or a universe, σ is a relational signature, and I is a function from σ to the set of all relations over A which assigns each relation symbol a corresponding relation over A. For simplicity, we will typically write a relational structure as (A;R1, . . . ,Rk) where each Ri is a relation over A, and will not make a sharp distinction between relations and their corresponding signatures. A set of relations Γ over A is a first-order reduct of a relational structure (A;R1, . . . ,Rk) if each R ∈ Γ is the set of models of a σ-formula (with equality) interpreted in (A;R1, . . . ,Rk). In symbols, we write R(x1, . . . , xn) ≡ ϕ(x1, . . . , xn) if R is the set of models of the first-order formula ϕ(x1, . . . , xn) with respect to the free variables x1, . . . , xn.

2.1 The Constraint Satisfaction Problem

Let Γ be a set of finitary relations over some set A of values, occasionally called a constraint language. The constraint satisfaction problem over Γ (CSP(Γ)) is defined as follows.

Instance: A set V of variables and a set C of constraints of the form R(x1, . . . , xk), where k is the arity of R,

x1, . . . , xk ∈ V and R ∈ Γ. Question: Is there a function f : V → A such that

(f(x1), . . . , f(xk)) ∈ R for every R(x1, . . . , xk) ∈ C?

Concerning representation, we take a simple approach and only consider the case when Γ is a first-order reduct of a relational structure, and represent each relation R ∈ Γ by a first-order formula. However, the exact representation is only important if Γ is infinite, since any reasonable representation can be chosen and precomputed if Γ is finite.

2.2 Primitive Positive Definitions and Interpretations

Let Γ be a constraint language over a domain A. A k-ary relation R is said to have a primitive positive definition (pp-definition) over Γ if R(x1, . . . , xk) ≡ ∃y1, . . . , yk′ : R1(x1) ∧ . . . ∧ Rm(xm) where each Ri ∈ Γ∪{EqA} and each xi is a tuple of variables over x1, . . . , xk, y1, . . . , yk′ matching the arity of Ri. Here, and in the sequel, EqA is the equality relation {(a, a) | a ∈ A)} over A. Thus, R is definable by a first-order formula consisting only of existential quantification and conjunction over positive atoms from Γ and equality constraints. If Γ is a constraint language we let 〈Γ〉 be the smallest set of relations containing Γ closed under pp-definitions. Pp-definitions are typically only useful for comparing similar languages over the same domain, but can be generalised as follows.

Definition 1. Let A and B be two domains and let Γ and ∆ be two constraint languages over A and B, respectively. A primitive positive interpretation (pp-interpretation) of ∆ over Γ consists of a d-ary relation F ⊆ Ad and a surjective function f : F → B such that F, f -1 (EqB) ∈ 〈Γ〉 and f -1 (R) ∈ 〈Γ〉 for every k-ary R ∈ ∆, where f -1 (R) denotes the (k ·d)-ary relation {(x11 , . . . , xd1 , . . . , x1k , . . . , xdk ) ∈ Ak·d | (f(x11 , . . . , xd1 ), . . . , f(x1k , . . . , xdk )) ∈ R}.

Hence, pp-interpretations are generalisations of ppdefinitions, and can be used to obtain polynomial-time reductions between CSPs (cf. Theorem 5.5.6 in [Bodirsky, 2012]).

2.3 Equality Languages

We say that Γ is an equality language if each R ∈ Γ admits a first-order definition over a relational structure (A; ∅), i.e. the empty structure. Recall here that the equality relation is always accessible in first-order logic. Without loss of generality we henceforth assume that A = N, write Eq (or = in infix notation) for the equality relation over N, and R̸= or ̸= (in infix notation) for the inequality relation {(x, y) ∈ N2 | x ̸= y} over N. The computational problem we consider is then CSP(Γ) when Γ is an equality language. This problem is easily seen to belong to NP for any finite language, and its classical complexity has been completely classified [Bodirsky and K´ara, 2008].

Theorem 1. Let Γ be an equality language. Then either CSP(Γ) is (1) polynomial-time solvable or (2) there exists a finite ∆ ⊆ Γ such that CSP(∆) is NP-complete since ∆ pp-interprets every finite-domain relation.

Example 1. Let S = {(x, x, y), (x, y, y) | x, y ∈ N, x ̸= y}, and observe that S(x, y, z) ≡ (x = y ∧ y ̸= z) ∨ (x ̸= y ∧ y = z). Thus, {S} is an equality language, and it is known that {S} pp-interprets a language ∆ where CSP(∆) is NP-hard, which implies that CSP({S}) is NP-hard, too. For tractability, if we take {Eq, R̸=} then CSP({Eq, R̸=}) is wellknown to be polynomial-time solvable. This can be proven via Theorem 1, but CSP({Eq,R̸=}) can also be solved by propagation methods.

2.4 Fine-Grained Complexity and the Exponential-Time Hypothesis

Assume that CSP(Γ) is NP-complete. How fast can we solve CSP(Γ), and is it possible to prove stronger lower bounds than an expected superpolynomial running time (under P ̸= NP)? Such questions, especially when the complexity parameter is the number of variables |V | or the number of constraints |C|, fall under the umbrella of fine-grained complexity. To prove non-trivial lower bounds for NP-complete problems we typically need stronger assumptions than P ̸= NP. Say that CSP(Γ) is solvable in subexponential time if CSP(Γ) is solvable in O(2ε|V | ) for each ε > 0. The conjecture that 3-SAT is not solvable in subexponential time is called the exponential-time hypothesis (ETH). There exists several stronger variants of the ETH. First, an algorithm A is said to be a 2c·|V | -randomised algorithm if its running time is bounded by 2c·|V | · poly(||I||) and its error probability is at most 1/3 (||I|| is the number of bits required to represent a CSP instance I). For k, d ≥ 1 we then define (1) ck = inf{c | ∃ a deterministic 2c·|V | algorithm for k-SAT} and (2) cd,k = inf{c | ∃ a 2c·|V | -randomised algorithm for CSP(Γd,k)}, where Γd,k is the set of all relations over the set {0, . . . , d - 1} of arity at most k. The randomised exponential-time hypothesis (r-ETH) is then the conjecture that c2,3 > 0, i.e., that 3-SAT is not solvable in subexponential time even with randomised algorithms, and the strong exponential-time hypothesis (SETH) is the conjecture that the limit of the sequence c3, c4, . . . is equal to 1.

3 Lower Bounds on the Complexity of Equality Constraints

In this section we investigate lower bounds for equality CSPs. As remarked in Section 1, such lower bounds are valuable since if it is possible to prove that CSP(Γ) is not solvable in O(f(|V |)) time (for some function f) then we cannot in general expect to solve CSP(∆) in O(f(|V |)) time when ∆ is a first-order reduct of an arbitrary relational structure. Let us recapitulate two known lower bounds.

Theorem 2. (1) If CSP(Γ) for an equality language Γ is NPhard then it is not solvable in subexponential time unless the ETH is false [Jonsson et al., 2017b, Thm. 9]) and (2) if Γ is the full first-order reduct of (N; ∅) then CSP(Γ) is not solvable in O(c|V | ) time for any c > 1 unless the SETH is false. (Theorem 19 in [Jonsson and Lagerkvist, 2017].)

3.1 Finite Versus Infinite Equality Languages

We begin by proving that for every c > 1 there exists a finite equality language Γc such that CSP(Γc) is not solvable in O(2c|V | ) time without contradicting the r-ETH. We first require the following result [Traxler, 2008, Thm. 1].

Theorem3. If r-ETHholds, then there exists a universal constant α > 0 such that for all d ≥ 3, α · log(d) ≤ cd,2.

Theorem 4. For every c > 1, there exists a finite equality language Γc such that CSP(Γc) cannot be solved in O(2c·|V | ) (randomised) time unless the r-ETH is false.

Proof. For 1 ≤ a, b ≤ d define Rd,a,b(c1, . . . , cd, x, y) ≡ ∨di=1 x = ci ∧ ∨di=1 y = ci ∧ (x ̸= ca ∨ y ̸= cb) . For arbitrary d then define the finite equality language Θd = {̸= }∪{Rd,a,b | 1 ≤ a, b ≤ d}. We present a polynomial-time reduction from CSP(Γd,2) to CSP(Θd) only introducing a constant number of fresh variables. Let (V,C) be an instance of CSP(Γd,2). Introduce d fresh variables c1, . . . , cd together with constraints {ci ̸= cj | 1 ≤ i < j ≤ d}. For each R(x, y) ∈ C, add the constraints Rd,a,b(c1, . . . , cd, x, y) for every 1 ≤ a, b ≤ d such that (a, b) ̸∈ R. The resulting instance (V ∪ {c1, . . . , cd},C ′ ) can be constructed in polynomial time, and is clearly satisfiable if and only if (V,C) is satisfiable. Furthermore, d is fixed so only a constant number of fresh variables are introduced. By Theorem 3, CSP(Θd) cannot be solved in 2(cd,2-ϵ)·|V | time for any ϵ > 0 unless r-ETH is false, and the result follows by choosing d such that cd,2 ≥ c. We know that α · log(d) ≤ cd,2 so it is sufficient to choose a d such that α · log(d) ≥ c, e.g. d = 2⌈ cα ⌉ .

Thus, assuming the r-ETH, there cannot exist an algorithm solving CSP(Γ) in O(c|V | ) time for every finite equality language Γ. This can be strengthened even further for infinite equality languages, and we will show the existence of Γ such that CSP(Γ) is not solvable in O(2o(|V | log |V |) ) time without contradicting the ETH. In contrast, the second statement of Theorem 2 is only valid under the much stronger SETH, and only if Γ consists of all first-order definable relations over (N; ∅). For this lower bound we provide a reduction from the k × k INDEPENDENT SET problem: given a graph G over the vertex set {1, . . . , k} × {1, . . . , k} (where k is part of the input), is there an independent set of size k in G with exactly one element from each row? The following lower bound is known under the ETH [Lokshtanov et al., 2018].

Theorem 5. k × k INDEPENDENT SET is not solvable in 2o(k log k) time unless the ETH is false.

For n ≥ 1 define Rn(y, x1, . . . , xn) ≡ y = x1 ∨ y = x2 ∨ · · · ∨ y = xn, and let R(x, y, z, w) ≡ x ̸= y ∨ z ̸= w. Let Γinf be the infinite equality language {̸=, R, R1, R2, . . .}.

Theorem 6. CSP(Γinf ) cannot be solved in 2o(|V | log |V |) time unless the ETH is false.

Proof. To prove the result, we present a polynomial-time reduction from k × k INDEPENDENT SET to CSP(Γinf) such that the resulting CSP(Γinf) instance only contains 2k variables. Let G = (V,E) denote an arbitrary graph where V = {1, . . . , k} × {1, . . . , k}. We then begin by introducing k variables a1, . . . , ak together with the constraints ai ̸= aj ,1 ≤ i < j ≤ k. Second, for each row 1 ≤ i ≤ k in G, introduce a variable xi and the constraint Rk(xi, a1, . . . , ak). This constraint ensures that xi equals one of the variables a1, . . . , ak. Third, for each edge e = ((a, b), (c, d)) ∈ E, introduce the constraint R(xa, ab, xc, ad). This constraint guarantees that both endpoints of an edge are not put into the independent set simultaneously.

Hence, we cannot even hope to solve CSP(Γ) in O(c|V | ) time for any c when Γ is allowed to be infinite. Furthermore, since an equality CSP is always solvable in 2O(|V | log |V |) time [Jonsson and Lagerkvist, 2017], the bound in Theorem 6 is asymptotically tight. Last, let us consider a problemwhich is related to equality CSPs, for which we rather effortlessly can obtain lower bounds by reducing from CSP(Γinf). Satisfiability modulo theories is a decision problem for logical formulas with respect to combinations of background theories expressed in classical first-order logic with equality. Let SMT(T ) be the problem of determining whether a first-order formula (with respect to a background theory T ) is satisfiable, and let SMT̸∀(T ) be the subproblem where universal quantifiers are not allowed. We can then readily prove a matching lower bound valid for any background theory T .

Lemma 1. SMT̸∀(∅) cannot be solved in 2o(|V | log |V |) time unless the ETH is false.

Proof. We present a polynomial-time reduction from CSP(Γinf ) which does not introduce any fresh variables. Let (V, C) be an instance of CSP(Γinf ), where V = {x1, . . . , xk} and C = {c1, . . . , cp}. Define F = ∃x1 . . . ∃xk : F1∧· · ·∧Fp where Fi = (¬(x = y)) if ci = x ̸= y, Fi = (y = x1 ∨ y = x2 ∨ . . . ∨ y = xn) if ci = Rn(y, x1, . . . , xn), and Fi = (¬(x = y) ∨ ¬(z = w)) if ci = S(x, y, z,w). It is obvious that F is true if and only if (V,C) has a solution, that F can easily be constructed in polynomial time, and that F contains as many variables as there are variables in V . The result then follows from Theorem 6.

To exemplify this, we consider the well-known unit two variable per inequality (UTVPI) class of constraints, i.e., SMT̸∀(UTVPI) where UTVPI for each integer b and coefficients c1, c2 ∈ {-1, 1} contains c1 · x + c2 · y ≥ b. The UTVPI class has many applications in, for instance, abstract interpretation, spatial databases, and theorem proving (cf. Schutt and Stuckey [2010] and the references therein.) It is known [Seshia et al., 2007] that SMT̸∀(UTVPI) can be solved in 2O(|V | log d) time where d = 2|V |(bmax + 1) + 1 and bmax is the maximum over the absolute values of constant terms in the constraints. Using Lemma 1 we can prove that this algorithm is close to optimal.

Theorem 7. SMT over UTVPI constraints, SMT̸∀(UTVPI), cannot be solved in 2o(n log d) time unless the ETH is false.

Proof. Assume there is an algorithm A that solves SMT̸∀(UTVPI) in 2o(|V | log d) time. The formulas constructed in Lemma 6 are SMT̸∀(UTVPI) formulas (degenerated ones, though, since they do not contain UTVPI constraints). Thus, bmax for this class X of formulas is 0, implying that A can solve SMT̸∀(UTVPI) restricted to X in 2o(n log n) time, contradicting Lemma 1.

3.2 No Easiest NP-Hard Infinite-Domain CSP

Our lower bounds suggest that equality CSPs are rather different from finite-domain CSPs when viewed under the lens of fine-grained complexity. In this section we prove yet another differentiating factor. For each finite A it is known that there exists ΓA such that CSP(ΓA) is NP-complete, but if an NP-complete CSP(∆)1 over A is solvable in O(c|V | ) time, then CSP(ΓA) is solvable in O(c|V | ) time, too [Jonsson et al., 2017b]. More generally, if G is a set of constraint languages over A, say that CSP(Γ) for Γ ∈ G is the easiest CSP problem in G if CSP(Γ) is solvable in O∗ (c|V | ) time whenever CSP(∆) for ∆ ∈ G is solvable in O∗ (c|V | ) time.

Contrary to the finite-domain case we will prove that there does not exist an easiest NP-complete equality CSP, unless the ETH is false. To prove this we for every c > 1 show the existence of an equality language Γc such that CSP(Γc) is NP-complete but solvable in O(c|V | ) time. First, recall from Example 1 that the ternary relation S = {(x, x, y), (x, y, y) | x, y ∈ N, x ̸= y} has an NP-complete CSP. We will show how S can be extended with additional arguments in order to decrease the time complexity of the resulting CSP. If v = (v1, . . . , vk) and w = (w1, . . . ,wk) are two k-ary tuples of variables, x a variable, and R is a binary relation, then we write R(x, v) for ∧1≤i≤k R(x, vi), R(v,w) for ∧1≤i,j≤k R(vi,wj), and R(v) for ∧1≤i,j≤k,i̸=j R(vi, vj). For each k ≥ 1 now define Sk (x, y, z, v,w) as ∧s∈{x,y,z},t∈{v,w} R̸=(s, t) ∧ R̸=(v,w) ∧ (x = y ∧ y ̸= z ∧ Eq(v) ∧ R̸=(w)) ∨ (x ̸= y ∧ y = z ∧ R̸=(v) ∧ Eq(w)) where v = (v1, . . . , vk) and w = (w1, . . . , wk) are two distinct k-ary tuples of variables. The problem CSP({Sk }) is clearly NP-complete since S ∈ 〈{Sk }〉, and we will now prove that the fine-grained complexity of CSP({Sk }) decreases, in the following sense.

Theorem 8. Let c > 1. Then there exists a k such that CSP({Sk }) is solvable in O∗ (c|V | ) time.

Proof. We will present an algorithm for CSP({Sk }) which runs in O∗ (2 nk ) time. The claim then follows when choosing sufficiently large k ≥ 1 log c . Thus, choose k ≥ 1 and let (V, C) be an instance of CSP({Sk }), where |V | = n. Say that a set of inequality constraints L is consistent if L, viewed as an instance of CSP({R̸=}), is satisfiable, and inconsistent otherwise. The consistency of a set of inequality constraints can be determined in polynomial time since CSP({R̸=}) is in P (from Example 1). Consider the following algorithm for CSP({Sk }), where the set L is used to keep track of inequality constraints induced by the constraints in the instance.

1. Let L = ∅.
2. If L is inconsistent, return no.
3. If L is consistent and C = ∅, return yes.
4. Pick a constraint Sk (xi, yi, zi, vi,wi) ∈ C where vi = (v1 i , . . . , vk i ) and wi = (w1 i , . . . ,wk i ).
5. Return no if:
6. (a) |{xi, yi, zi}| = 1,
7. (b) {xi, yi, zi} ∩ {v1 i , . . . , vk i ,w1 i , . . . ,wk i } ̸= ∅,
8. (c) {v1 i , . . . , vk i } ∩ {w1 i , . . . ,wk i } ̸= ∅, or if
9. (d) |{v1 i , . . . , vk i }| < k and |{w1 i , . . . ,wk i }| < k.

1 For technical reasons ∆ contains all unary relations over A.

1. If |{v1 i , . . . , vk i }| < k and |{w1 i , . . . ,wk i }| = k then we identify yi with xi, v1 i with every variable in {v1 i , . . . , vk i } \ {v1 i }, remove Sk (xi, yi, zi, vi,wi), add R̸=(wi), R̸=(xi, vi), R̸=(xi, wi), R̸=(zi, vi), R̸=(zi, wi), R̸=(xi, zi) to L, and jump to step (2).
2. The case |{v1 i , . . . , vk i }| = k, |{w1 i , . . . ,wk i }| < k, is handled analogously.
3. If none of the above cases apply we proceed as follows.
4. (a) If |{xi, yi, zi}| = 2 then no branching is necessary, and depending on whether xi = yi or xi ̸= yi we jump to step (b) or step (c) below.
5. (b) Identify yi with xi, vj i (2 ≤ j ≤ k) with v1 i , add R̸=(wi),R̸=(xi, vi),R̸=(xi,wi),R̸=(zi, vi), R̸=(zi,wi), and R̸=(xi, zi)} to L, remove Sk (xi, yi, zi, vi,wi), and jump to step (2).
6. (c) Identify zi with yi, wj i (2 ≤ j ≤ k) with w1 i , add R̸=(vi), R̸=(xi, vi), R̸=(xi, wi), R̸=(yi, vi), R̸=(yi,wi), and R̸=(xi, yi) to L, remove Sk (xi, yi, zi, vi, wi), and jump to step (2).
7. Answer yes if any of the two recursive branches return yes, and otherwise no.

For correctness, the algorithm branches on a constraint Sk (xi, yi, zi, vi,wi) ∈ C, and either identifies xi with yi, or yi with zi, and in the process identifies variables and introduces inequality constraints according to the definition of Sk . Furthermore, the algorithm answers 'yes' if and only if it for each constraint Sk (xi, yi, zi, vi, wi) ∈ C is possible to identify xi with yi, or yi with zi, in a non-contradictory way, and answers 'no' if and only if this is not possible. Concerning time complexity, note first that all variables in vi and wi are distinct, once step (8) is reached. This follows from the tests undertaken in step 5 where we systematically verify that {w1 i , . . . ,wk i } and {v1 i , . . . , vk i } are disjoint and that |{w1 i , . . . ,wk i }| = |{v1 i , . . . , vk i }| = k. Furthermore, if (8)(b) or (8)(c) is reached then |{xi, yi, zi}| = 3, as otherwise the current instance is unsatisfiable (|{xi, yi, zi}| = 1) or no branching was required (|{xi, yi, zi}| = 2). Thus, in each branch we eliminate k variables via variable identification, which implies that the time complexity is bounded by the recurrence T(n) = 2T(n - k) + poly(||I||). Thus, the total running time is O∗ (2 nk ), which solves CSP({Sk }) in O∗ (cn ) time for sufficiently large k.

We immediately obtain the following corollary.

Corollary 1. Let A = (A; R1, . . . , Rk) be a relational structure over a countably infinite A, such that CSP(Γ) for a first-order reduct of A is NP-complete if and only if Γ ppinterprets 3-SAT. Let G = {Γ | Γ is a first-order reduct of A and CSP(Γ) is NP-complete}. If G has an easiest CSP problem then the ETH is false.

Proof. For each c > 1 there exists a constraint language Γc ∈ G such that CSP(Γc) is NP-complete and solvable in O∗ (c|V | ) time (Theorem 8). If G has an easiest NP-complete problem CSP(Γ) then (1) CSP(Γ) pp-interprets 3-SAT, and (2) CSP(Γ) is solvable in O∗ (c|V | ) time for each c > 1. Thus, CSP(Γ) is solvable in subexponential time, but this violates the ETH by Corollary 10 in [Jonsson et al., 2017b].

This captures the NP-hard cases of the CSP dichotomy conjecture over finitely bounded homogeneous structures [Barto and Pinsker, 2016].

4 Upper Bounds for Equality CSPs

The lower bounds established in Section 3 suggest that we cannot construct an O(c|V | ) time algorithm (c > 1) which is applicable to arbitrary equality languages. However, if we fix a finite equality language Γ, this still leaves the possibility of constructing an O(c|V | ) time algorithm for a constant c depending on Γ. We manage to construct a novel algorithm for CSP(Γ), where Γ is a finite equality language with maximum arity α, with a running time of O∗ (( α(α-1) 2 )|V | ). Thus, the algorithm runs in O∗ (c|V | ) time for a constant c depending on Γ, which is a significant improvement over the algorithm proposed by [Jonsson and Lagerkvist, 2017] which solves CSP(Γ) in O∗ (2|V |·log( 0.792|V | ln(|V |+1) ) ) time.

Theorem 9. Let Γ be a finite equality language and let α = max{ar(R) | R ∈ Γ}. Then, CSP(Γ) can be solved in O∗ (( α(α-1) 2 )|V | ) time.

Proof. Consider the following algorithmA(I) for an instance I of CSP(Γ).

1. Let I = (V,C) and let V = {x1, . . . , xn}.
2. Define s: V → {1, . . . , n} such that s(xi) = i.
3. If s is a solution to I, then return 'yes'.
4. If s is not a solution to I and |V | = 1, then return 'no'.
5. Arbitrarily choose a constraint R(xi1 , . . . , xip ) that is not satisfied by s.
6. For each 1 ≤ j < k ≤ p, let Ij,k denote the instance obtained by identifying xij with xik in I.
7. (a) If A(Ij,k) = 'yes' then return 'yes'.
8. Return 'no'.

We begin by proving correctness by induction over |V | = n. If n = 1, then the tests in steps (3) and (4) provide the correct answer. Assume the algorithm is correct when n = m > 1. Let I = (V,C) be an instance where |V | = n = m+ 1. First, assume that I has an injective solution. Then it is readily verified that f : {1, . . . , |V |} defined as f(xi) = i for each xi ∈ V = {x1, . . . , x|V |}, is a solution to I as well (in technical terms this follows from the well-known fact that the automorphisms of Γ is the full symmetric group [Bodirsky and K´ara, 2008]). Hence, the algorithm answers 'yes' via step (3). Otherwise I does not have an injective solution and at least one constraint c = R(xi1 , . . . , xip ) ∈ C is not satisfied by the function s. This implies that (at least) two variables in {xi1 , . . . , xip } must be assigned the same value. This is systematically tested in step (6), and the correctness follows from the inductive hypothesis.

Concerning the time complexity, it is bounded from above by the recurrence T(n) = α(α-1) 2 · T(n - 1) + poly(||I||)

since ip ≤ α for each possible choice of constraint R(xi1 , . . . , xip ). Thus, T(n) ∈ O∗ (( α(α-1) 2 )n ), and we get the desired bound on the time complexity.

5 Concluding Remarks

We have studied fine-grained complexity of infinite-domain equality CSPs, and have proven that this class of problems differ from finite-domain CSPs in almost every way conceivable. Despite the disarray of this complexity landscape, it is possible to outline several concrete future research directions. First, since we know that all finite equality languages can be solved in O(c|V | ) time and that there exists infinite equality languages not solvable in O(c|V | ) time for any c > 1, is it possible to prove a dichotomy separating the problems solvable in O(c|V | ) time to those that are not?

More generally, which infinite-domain CSPs are solvable in O(c|V | ) time? Is this strictly a property of finite firstorder reducts (disregarding trivial examples of infinite language which can be constructed by adding an infinite number of relations which do not affect the complexity)? An interesting continuation is the class of temporal CSPs, i.e., CSPs over first-order reduct of (Q;<). Temporal languages are wellbehaved from a model theoretic viewpoint (ω-categorical), admit a dichotomy between P and NP-complete, and are always solvable in O∗ (2|V | log |V | ) time, so one would expect similarities between equality CSPs and temporal CSPs when it comes to fine-grained complexity. Thus, which temporal CSPs are solvable in O(c|V | ) time? Despite the aforementioned similarities there are still large differences to equality CSPs. For example, there exists a finite first-order reduct Γ of (Q; <) such that CSP(Γ) is not solvable in 2o(|V | log |V | ) time

without violating the r-ETH [Jonsson and Lagerkvist, 2018].

Last, we have seen that the class of NP-complete equality CSPs does not admit an "easiest problem" without violating the ETH, contrary to satisfiability problems [Jonsson et al., 2017a] and finite-domain CSPs [Jonsson et al., 2017b]. The existence of easiest problems of this form can be explained by so-called weak bases. We brush aside the technical definition and simply remark that a weak base is a constraint language Γ implying that CSP(Γ) is the easiest CSP problem with respect to the set of constraint languages that can pp-define (and be pp-defined by) Γ. A weak base Γ such that 〈Γ〉 is the full firstorder reduct E of (N; ∅) would therefore be a great surprise since it, in the light of Theorem 8, would contradict the ETH. However, it is in fact possible to unconditionally prove that E does not have a weak base, using techniques from partial clone theory. In general, both positive and negative examples of infinite-domain weak bases exist [Romov, 2018], but the resulting CSPs are not of practical interest. Thus, does there exist 〈Γ〉 over a countably infinite domain admitting a weak base, and where CSP(Γ) is NP-hard?

Acknowledgements

The authors are partially supported by the Swedish Research Council (VR) under grant 2017- 04112. In addition, Victor Lagerkvist is partially supported by the Swedish Research Council (VR) under grant 2019-03690.