Satisfiability of Commutative vs. Non-Commutative CSPs

CSPs capture some of the most fundamental computational problems, including graph and hypergraph colorings, linear equations, and variants and generalizations of satisfiability. Informally, one is given a set of variables and a set of constraints, each depending only on constantly many variables. Given a CSP instance, the goal is to find an assignment of values to all the variables so that all constraints are satisfied. For example, if the domain is $\{r,g,b\}$ and the constraints are of the form $R(x,y)$, where $R=\{(r,g),(g,r),(g,b),(b,g),(r,b),(b,r)\}$ is the binary disequality relation on $\{r,g,b\}$, we obtain the classic graph 3-Colorability problem. If the domain is $\{r,g,b,o\}$ and the constraints are of the form $R(x,y)$, where $R=\{(r,g),(g,r),(g,b),(b,g),(b,o),(o,b),(o,r),(r,o)\}$, we obtain a variant of the graph 4-Colorability problem in which adjacent vertices must be assigned different colors and, additionally, red and blue vertices must not be adjacent and green and orange vertices must not be adjacent.

Back in 1978, Schaefer famously classified all Boolean CSPs as solvable in polynomial time or NP-hard [58].¹¹1We call a CSP Boolean if the domain of all variables is of size two. Some papers call such CSPs binary. We use the term binary for a relation of arity two and for CSPs whose constraints involve binary relations. The tractable cases are the standard textbook problems, namely 2-SAT, Horn-SAT, dual Horn-SAT, and system of linear equations on a two-element set.²²2There are also two trivial, uninteresting cases called 0-valid and 1-valid. Hell and Nešetřil studied a special case of CSPs known as graph homomorphisms [34]. These are CSPs in which all constraints involve the same binary symmetric relation, i.e., a graph. The above-mentioned 3-Colorability problem is the homomorphism problem to $K_3$, the undirected clique on three vertices, say $\{r,g,b\}$. The above-mentioned variant of 4-Colorability is the homomorphism problem to $C_4$, the undirected cycle on four vertices, say $\{r,g,b,o\}$. Generalizing greatly the classic result of Karp that $k$-Colorability is solvable in polynomial time for $k\le 2$ and NP-hard for $k\ge 3$ and other concrete problems such as the (tractable) variant of 4-Colorability above, Hell and Nešetřil obtained in 1990 a complete classification of such CSPs [33]. Motivated by these two results and the quest to identify the largest subclass of NP that could exhibit a dichotomy and thus avoid NP-intermediate cases, Feder and Vardi famously conjectured that all CSPs on finite domains admit a dichotomy; i.e., are either solvable in polynomial time or are NP-hard [27].

Following the so-called algebraic approach to CSPs, pioneered by Jeavons, Cohen and Gyssens [35] and Bulatov, Jeavons, and Krokhin [12], the conjecture was resolved in the affirmative in 2017 by Bulatov [16] and, independently, by Zhuk [65, 66]. The algebraic approach allows for a very clean and precise characterization of what makes certain CSPs computationally tractable – this is captured by the notion of polymorphisms, which can be thought of as multivariate symmetries of solutions spaces of CSPs. Along the way to the resolution of the Feder-Vardi dichotomy conjecture, the algebraic approach has been successfully used to establish other results about CSPs, e.g., characterizing the power of local consistency algorithms for CSPs [11, 3], characterizing robustly solvable CSPs [31, 24, 4], classifying the complexity of exact optimization CSPs [61, 42], the tremendous progress on classifying the complexity of CSPs on infinite domains [7], and very recently using SDPs for robustly solving certain promise CSPs [9].

Consider the following instance of a Boolean CSP, consisting in nine variables $x_1,\mathrm{\dots },x_9$ over the Boolean domain $\{-1,+1\}$ and the following six constraints:

Graphically, this system of equations can be represented by a square, where each equation on the left of (1) comes from a row, and each equation on the right of (1) comes from a column.

The system of equations (1) has no solution in the Boolean domain $\{-1,+1\}$: By multiplying the left-hand sides of all equations we get $+1$ because every variable occurs twice in the system and $x_i^2=+1$ for every $1\le i\le 9$. However, by multiplying the right-hand sides of all equations, we get $-1$. Note that this argument used implicitly the assumption that the variables commute pairwise even if they do not appear in the same equation, which is true over $\{-1,+1\}$. Thus, this argument does not hold if one assumes that only variables occurring in the same equation commute pairwise. In fact, Mermin famously established that the system (1) has a solution consisting of linear operators on a Hilbert space of dimension four [50, 51] and the construction is now know as the Mermin-Peres magic square [54]. This construction proves the Bell-Kochen-Specker theorem on the impossibility to explain quantum mechanics via hidden variables [6, 39].

Any Boolean CSP instance, just like the one above, can be associated with a certain non-local game with two players, say Alice and Bob, who are unable to communicate while the game is in progress. Alice is given a constraint at random and must return a satisfying assignment to the variables in the constraint. Bob is given a variable from the constraint and must return an assignment to the variable. The two players win if they assign the same value to the chosen variable. With shared randomness, Alice and Bob can play the game perfectly if and only if the instance is satisfiable [22]. The Mermin-Peres construction [50, 54] was the first example of an instance where the players can play perfectly by sharing an entangled quantum state although the instance is not satisfiable. We note that [50, 54] were looking at quantum contextuality scenarios rather than non-local games and it was Aravind who reformulated the construction in the above-described game setting [1], cf. also [20]. The game was studied systematically for Boolean CSP by Cleve and Mittal [22] and further studied by Cleve, Liu, and Slofstra [21].

Every Boolean relation can be identified with its characteristic function, which has a unique representation as a multilinear polynomial via the Fourier transform. The multilinear polynomial representation of Boolean relations (and thus also Boolean CSPs) makes it possible to consider relaxations of satisfiability in which the variables take values in a suitable space, rather than in $\{-1,+1\}$. Such relaxations of satisfiability have been considered in the foundations of physics long ago, playing an important role in our understanding of the differences between classical and quantum theories. In detail, given a Boolean CSP instance, a classical assignment assigns to every variable a value from $\{-1,+1\}$. An operator assignment assigns to every variable a linear operator $A$ on a Hilbert space so that $A^2=I$ and each $A$ is self-adjoint, i.e., $A=A^{\ast }$ and thus in particular $A$ is normal, meaning that $A{A}^{\ast }=A^{\ast }A$.³³3For finite-dimensional Hilbert spaces, a linear operator is just, up to a choice of basis, a matrix with complex entries, and the adjoint $A^{\ast }$ of $A$ is the conjugate transpose of $A$, also denoted by $A^{\ast }$. For infinite-dimensional Hilbert spaces, the notions are more involved, cf. Section 2 for all details. Furthermore, it is required that operators assigned to variables from the scope of some constraint should pairwise commute.

Ji showed that for Boolean CSPs corresponding to 2-SAT there is no difference between (classical) satisfiability and satisfiability via operators [36]. Later, Atserias, Kolaitis, and Severini established a complete classification for all Boolean CSPs parameterized by the set of allowed constraint relations. In particular, using the substitution method [22] they showed that that only CSPs whose relations are 0-valid, 1-valid, or come from 2-SAT, Horn-SAT, or Dual Horn-SAT have “no satisfiability gap” in the sense that (classic) satisfiability is equivalent to operator satisfiability (over both finite- and infinite-dimensional Hilbert spaces) [2]. For all other Boolean CSPs, Atserias et al. [2] showed that there are satisfiability gaps in the following sense: There are instances that are not (classically) satisfiable but are satisfiable via operators on finite-dimensional Hilbert spaces, relying on the Mermin-Peres magic square – gaps of the first kind. This immediately implies that there are instances that are not (classically) satisfiable but are satisfiable via operators on infinite-dimensional Hilbert spaces – gaps of the second kind. Finally, there are instances that are not satisfiable via operators on finite-dimensional Hilbert spaces but are satisfiable via operators on infinite-dimensional Hilbert spaces, relying on the breakthrough result of Slofstra who proved this for linear equations [59] – gaps of the third kind. The result is established in [2] by showing that reductions between CSPs based on primitive positive formulas, which preserve complexity and were used to establish Schaefer’s classification of Boolean CSPs [58], preserve satisfiability gaps.

As our main contribution, we generalize the result of Atserias et al. [2] from Boolean CSPs to CSPs on arbitrary finite domains. As has been done in, e.g, [23, 30, 56], we represent a finite domain of size $d$ by the $d$-th roots of unity, and require that each operator $A$ in an operator assignment should be normal (i.e. $A{A}^{\ast }=A^{\ast }A$) and should satisfy $A^d=I$. The representation of non-Boolean CSPs relies on multi-dimensional Fourier transform. Our main result is a partial classification of satisfiability gaps for CSPs on arbitrary finite domains, with the remaining cases being related to a well-known open problem in the area, which is the existence of gap instances of the first kind for linear equations over ${\mathbb{Z}}_p$ with $p>2$.

In detail, as our first result we prove that NP-hard CSPs do have gaps of all three kinds. Second, we show that CSPs of bounded width (on arbitrary finite domains) do not have a satisfiability gap (of any kind), meaning that classical satisfiability is equivalent to satisfiability via operators on finite- and infinite-dimensional Hilbert spaces. Third, all other CSPs (i.e., tractable CSPs of unbounded width) can simulate, in a precise technical sense, linear equations over an Abelian group of prime order $p$. We prove that these simulations preserve satisfiability gaps. Thus, we obtain a satisfiability gap of the second kind by the result from an upcoming paper by Slofstra and Zhang [60]. Moreover, for $p=2$, we obtain a satisfiability gap of the first kind (and thus also of the second kind) from the Mermin-Peres magic square [50, 51, 54], and a satisfiability gap of the third kind from Slofstra’s result [59]. Finally, the reductions will also establish the first claim, gaps of all three kinds for NP-hard CSPs via [50, 51, 54, 59].

We note that Theorem 1 implies a classification of Boolean CSPs, thus recovering the result by Atserias et al. [2]. Indeed, a Boolean language $\mathrm{\Gamma }$ that is 0-valid, 1-valid, or comes from 2-SAT, Horn-SAT, or Dual Horn-SAT has bounded width; also, for a Boolean $\mathrm{\Gamma }$ one gets $p=2$ in Theorem 1 (2b).

Theorem 1 also implies a classification for CSPs on graphs (such CSPs are also known as $H$-Coloring problems): If $\mathrm{\Gamma }=\{R\}$, where $R$ is a binary symmetric relation, then either $R$ is bipartite or not. In the former case, $\mathrm{CSP}(\mathrm{\Gamma })$ has bounded width [17] and thus has no gaps of any kind. In the latter case, $\mathrm{CSP}(\mathrm{\Gamma })$ is NP-hard [33, 14] and thus has gaps of all three kinds.

We note that the remaining cases not covered by Theorem 1 (i.e., $\mathrm{CSP}(\mathrm{\Gamma })$ that are tractable but have unbounded width and can simulate linear equations over an Abelian group of prime order $p>2$ but not of order $2$) relate to the known difficulties of establishing satisfiability gaps of the first kind for linear equations over ${\mathbb{Z}}_p$ with $p>2$, e.g., there are results showing that such an instance cannot be obtained from generalized Pauli matrices [56] and beyond [29].⁴⁴4We remark that our results show that one can obtain gap instances from homomorphic preimages of already established gap instance (cf. Step 4 in [18]).

The proof of Theorem 1 relies on several ingredients. Firstly, we observe that results establishing that primitive positive definability preserve satisfiability gaps [2] can be lifted from Boolean to arbitrary finite domains.⁵⁵5[49, Theorem 6.4] considers subdivisions, a special case of conjunctive definitions, which in turn are a special case of primitive positive definitions (without existential quantifiers). Our result shows that [49, Theorem 6.4] extends to conjunctive definitions. Secondly, for CSPs of bounded width we show that there is no difference between classical and operator satisfiability by simulating the inference by the so-called Singleton Linear Arc Consistency (SLAC) algorithm in polynomial equations. We note that while there are several (seemingly stronger) algorithms for CSPs of bounded width, our proof relies crucially on the special structure of SLAC and the breakthrough result of Kozik that SLAC solves all CSPs of bounded width [43]. Thirdly, to prove that NP-hard CSPs and certain CSPs of unbounded width have satisfiability gaps we use the algebraic approach to CSPs, namely, we show that not only primitive positive definitions but also other reductions, namely going to the core, adding constants, and restrictions to subalgebras and factors, preserve satisfiability gaps.

We note that there is a significant hurdle to go from Boolean CSPs to CSPs over arbitrary finite domains. While any non-Boolean CSP can be Booleanized via indicator variables and extra constraints, such constructions do not immediately imply classifications of non-Boolean CSPs as the “encoding constraints” are intended to be used in only a particular way. Indeed, while the complexity of Boolean CSPs was established by Schaefer in 1978 [58] and the complexity of CSPs on three-element domains was established by Bulatov in 2002 [13, 15], the dichotomy for all finite domains was only established in 2017 [16, 65, 66]. Similarly for other variants of CSPs and different notions of tractability, results on Boolean domains, including the work of Atserias et al. [2], rely crucially on the explicit knowledge of the structure of relations on Boolean domains (established by Post [55]), which is not known for non-Boolean CSPs. Indeed, on the tractability side, the structure of relations in tractable Boolean CSPs is simple and very well understood; on the intractability side, reductions based only on primitive positive definitions suffice for a complete classification of Boolean CSPs. Neither of these two facts is true for non-Boolean CSPs.

We find it fascinating that bounded width might be the borderline for satisfiability gaps for CSPs, thus linking a notion coming from a natural combinatorial algorithm for CSPs with a foundational topic in quantum computation. Indeed, if satisfiability gaps of the first kind exist for linear equations over ${\mathbb{Z}}_p$ with $p>2$ then our main result implies that all CSPs of unbounded width admit satisfiability gaps of all three kinds. This is yet another result indicating the fundamental nature of bounded width, which captures not only the power of the local consistency algorithm [45, 48, 11, 3] as conjectured in [27] with links to Datalog, pebble games, and logic [27, 41], but also robust solvability of CSPs [4], exact solvability of valued CSPs by LP [62] and SDP [63] relaxations, and now also possibly satisfiability via operators.

Paddock and Slofstra [53] streamlined the results from [2], and also gave an overview of other notions of satisfiability and their relationship, including the celebrated MIP^∗=RE result of Ji et al. [37, 38]. Further, Culf, Mousavi, and Spirig recently studied approximability of operator CSPs [23]. While we used the magic square to construct a gap of the first kind, other systems based on linear equations could be used instead, e.g. the pentagram and the BCS in [59], cf. also [64]. Finally, we note that the notion of quantum homomorphism from the work of Mančinska and Roberson [47], as well as the recent work of Ciardo [19], is different from ours except when $d=2$. In the case of $d=2$, as considered in [2], operator assignments have to be self-adjoint and can be transformed to quantum isomorphisms. When $d\ge 3$, the straightforward translation through Fourier transform in cyclic groups result in projectors that are not self-adjoint, and therefore do not give rise to a quantum isomorphism. However, the overall results are somewhat similar, e.g., Ciardo shows [19] that CSPs of bounded width have no quantum advantage (over finite-dimensional spaces) by establishing a so-called minion homomorphism – relying crucially on idempotency – to the minion capturing the basic SDP relaxation, which is known to solve CSPs of bounded width by the work of Barto and Kozik [4]. The methods used in [19] rely, unlike methods and results in this paper, on being in the finite-dimensional case.

An instance of the constraint satisfaction problem (CSP) is a triple $𝒫=(V,D,𝒞)$, where $V$ is a set of variables, $D$ is a set of domain values, and $𝒞$ is a set of constraints. Every constraint in $𝒞$ is a pair $⟨𝐬,R⟩$, where $𝐬\in V^r$ is the constraint scope and $R\subseteq D^r$ is the constraint relation of arity $r=ar(R)$. Given a CSP instance $𝒫$, the task is to determine whether there is an assignment $s:V\to D$ that assigns to every variable from $V$ a value from $D$ in such a way that all the constraints are satisfied; i.e., $(s(v_1),\mathrm{\dots },s(v_r))\in R$ for every constraint $⟨(v_1,\mathrm{\dots },v_r),R⟩\in 𝒞$. An assignment satisfying all the constraints is also called a solution.

Let $D$ be a fixed finite set. A finite set $\mathrm{\Gamma }$ of relations over $D$ is called a constraint language over $D$. We denote by $\mathrm{CSP}(\mathrm{\Gamma })$ the class of CSP instances in which all constraint relations belong to $\mathrm{\Gamma }$. A mapping $\varrho :D\to D$ is an endomorphism or unary polymorphism of $\mathrm{\Gamma }$ if, for any $R\in \mathrm{\Gamma }$ (say, $r$-ary) and any $(a_1,\mathrm{\dots },a_r)\in R$, the tuple $(\varrho (a_1),\mathrm{\dots },\varrho (a_r))$ belongs to $R$.

Intuitively, CSPs of bounded width are those CSPs for which unsatisfiable instances can be refuted via local propagation. An obvious obstruction to bounded width, in addition to NP-hard CSPs, is CSPs encoding systems of linear equations [27]. A celebrated result of Barto and Kozik established that CSPs of bounded width are precisely those CSPs that cannot simulate, in a precise sense, linear equations [3]. While bounded width has several characterizations [45, 48, 11, 3, 44],⁶⁶6One characterization implies that checking whether a constraint language has bounded width is decidable [44]. we will rely on the result of Kozik [43] that established that every CSP of bounded width can be solved through constraint propagation of a very restricted type, so-called Singleton Linear Arc-Consistency (SLAC).

In order to explain SLAC, we need to start with Arc-Consistency (AC). AC is one of the basic levels of local consistency notions. It is a property of a CSP and also an algorithm turning an instance $𝒫\in \mathrm{CSP}(\mathrm{\Gamma })$ into an equivalent subinstance ${𝒫}^{\prime }\in \mathrm{CSP}(\mathrm{\Gamma })$ that satisfies the AC property. Intuitively, given an instance $𝒫=(V,D,𝒞)\in \mathrm{CSP}(\mathrm{\Gamma })$, the AC algorithm starts with setting the domain $D_v=D$ for every variable $v\in V$. Then, it prunes the sets ${\{D_v\}}_{v\in V}$ in an iterative fashion, terminating (in polynomial time in the size of $𝒫$) with a maximal subinstance of $𝒫$ that satisfies the AC condition; namely, for every variable $v\in V$, every value $a\in D_v$, and every constraint $⟨𝐬,R⟩\in 𝒞$ such that $𝐬[i]=v$ for some $i$, there is a tuple $𝐚\in R$ with $𝐚[i]=a$. The resulting subinstance ${𝒫}^{\prime }$ is equivalent to $𝒫$ in the sense that $𝒫$ has a solution if and only if ${𝒫}^{\prime }$ has a solution. We say that AC solves an instance $𝒫$ if $𝒫$ has a solution whenever ${𝒫}^{\prime }$ is consistent; i.e., none of the sets $D_v$ in ${𝒫}^{\prime }$ is empty. AC is not strong enough to solve all CSPs of bounded width (e.g., 2-SAT) but its full power is understood [27, 25].

Equivalently, Arc-Consistency can be described in terms of a Datalog program [40]. In general, a Datalog program derives facts about an instance $𝒫\in \mathrm{CSP}(\mathrm{\Gamma })$ using a fixed set of rules that depend on the constraint language $\mathrm{\Gamma }$. The rules are defined using relations from $\mathrm{\Gamma }$ called extensional databases (EDBs) as well as a number of auxiliary relations called intensional databases (IDBs). Each rule consists of a head, which is a single IDB, and the body, which is a sequence of IDBs and EDBs. The execution of the program updates the head IDB whenever the body of the rule is satisfied, that is, every EDB and IDB in the body is satisfied. The computation of the program ends when no relation can be updated, or when the goal predicate is reached. If we require that a Datalog program should only include unary IDBs and that every rule should have at most one EDB then the power of the program for CSPs amounts to AC. In detail, the AC Datalog program has a unary relation (IDB) $T_S(v)$ for each subset $S\subseteq D$. Then for every $⟨(v_1,\mathrm{\dots },v_r),R⟩\in 𝒞$ and for any IDBs $T_{S_1},\mathrm{\dots },T_{S_m},T_S$ the program contains the rule

if for any $𝐚\in R$ such that $𝐚[i_j]\in S_j$ we have $𝐚[i]\in S$. The Arc-Consistency algorithm is Linear if $m=1$ for every rule in the corresponding Datalog program.

The Singleton Arc-Consistency (SAC) algorithm is a modification of the AC algorithm [26]. SAC updates the sets ${\{D_v\}}_{v\in V}$ as follows: it removes $a$ from $D_v$ if the current instance augmented with the constraint fixing the value $a$ to the variable $v$ is found inconsistent by the AC algorithm. Finally, the Singleton Linear Arc-Consistency algorithm is a modification of SAC (due to Kozik [43] and Zhuk [66]) that uses the Linear AC algorithm rather than the AC algorithm. Kozik has shown that SLAC solves all CSPs of bounded width [43]. As with AC, SLAC is not only an algorithm but also a condition (of the instance ${𝒫}^{\prime }$ produced by the algorithm). We say that an instance $𝒫$ is SLAC-consistent if the SLAC algorithm, given in Algorithm 1, does not change the instance.

Let $U_d$ be the set of $d$-th roots of unity, that is, . The Fourier transform (FT) of a function $f:U_d^n\to U_d$ is defined, for $𝐚\in U_d^n$, as $FT(f,𝐚)={\sum }_{𝐛\in U_d^n}f(𝐛){\lambda }_1^{𝐚\cdot 𝐛}$. Then it is not hard to see that $f(𝐚)={\sum }_{𝐛\in U_d^n}FT(f,𝐛){\lambda }_1^{𝐚\cdot 𝐛}$, which gives rise to a representation of $f$ by a polynomial

where ${𝐛}^{\prime }=(k_1,\mathrm{\dots },k_n)$ and $𝐛[j]={\lambda }_{k_j}$. This representation is unique [52].

Let $V$ be a complex vector space. A linear operator on $V$ is a linear map from $V$ to $V$. The identity linear operator on $V$ is denoted by $I$. The linear operator that is identically $0$ is denoted by $0$. Let $A$ and $B$ be two linear operators. Their pointwise addition is denoted by $A+B$, their composition is denoted by $AB$, and the pointwise scaling of $A$ by a scalar $c\in ℂ$ is denoted by $cA$. All of these are linear operators and thus we can plug linear operators in a polynomial $P$. We say that operators $A$ and $B$ commute if $AB=BA$. A collection of linear operators $A_1,\mathrm{\dots },A_n$ pairwise commute if $A_i{A}_j=A_j{A}_i$ for every $i,j\in [n]$. If $A_1,\mathrm{\dots },A_n$ pairwise commute then $P(A_1,\mathrm{\dots },A_n)$ is well defined. $ℂ[x_1,\mathrm{\dots },x_n]$ denotes the ring of polynomials with complex coefficients and commuting variables $x_1,\mathrm{\dots },x_n$. A linear operator is bounded if it maps bounded subsets to bounded subsets. Let $A$ be a densely defined linear operator, i.e., $A$ is defined almost everywhere. We denote by $A^{\ast }$ its adjoint [28] and call $A$ normal if $A$ commutes with its adjoint, i.e., $A{A}^{\ast }=A^{\ast }A$. A linear operator $U$ is called unitary if $U{U}^{\ast }=U^{\ast }U=I$, the identity operator.

A Hilbert space is a complex vector space with an inner product whose norm induces a complete metric. All Hilbert spaces of finite dimension $d$ are isomorphic to ${ℂ}^d$ with the standard complex inner product. Thus, after the choice of basis, linear operators on a $d$-dimensional Hilbert space can be identified with matrices in ${ℂ}^{d\times d}$, and operator composition becomes matrix multiplication. Thus, for Hilbert spaces of finite dimension we will freely switch between the operator and matrix terminology. A diagonal matrix has all off-diagonal entries equal to $0$. For a matrix $A$, the adjoint operator $A^{\ast }$ is the conjugate transpose. Recall that ${(AB)}^{\ast }=B^{\ast }{A}^{\ast }$. We will use the following form of the so-called strong spectral theorem.

In the infinite-dimensional case, the Strong Spectral Theorem is more complicated. Firstly, it involves general $L^2$- and $L^{\mathrm{\infty }}$-spaces. Let $(\mathrm{\Omega },ℳ,\mu )$ be a measure space, i.e., $\mathrm{\Omega }$ is a set, $ℳ$ is a $\sigma$-algebra on the set $\mathrm{\Omega }$ (i.e. $ℳ$ is a nonempty collection of subsets of $\mathrm{\Omega }$ containing $\mathrm{\Omega }$ and closed under complements, countable intersections, and countable unions), and $\mu$ is a measure on $(\mathrm{\Omega },ℳ)$ (i.e. $\mu$ is nonnegative and countably additive). Then $L^2(\mathrm{\Omega },\mu )$ denotes the collection of square integrable measurable functions, up to almost everywhere equality, and $L^{\mathrm{\infty }}(\mathrm{\Omega },\mu )$ denotes the collection of essentially bounded measurable functions, up to almost everywhere equality; all measure-theoretic terms in these definitions refer to $\mu$, cf. [28] for details. Instead of diagonal matrices, the General Strong Spectral Theorem uses multiplication operators on a $L^2(\mathrm{\Omega },\mu )$-space. Let $V$ be a complex vector space of functions mapping an index set $X$ to $ℂ$. A multiplication operator of $V$ is a linear operator whose value at a function $f:X\to ℂ$ in $V$ is given by pointwise multiplication by a fixed function $a:X\to ℂ$. In other words, the multiplication operator given by $a$ is

One part of our main result is the following.

The main idea behind the proof of Theorem 6 is to simulate the inference provided by SLAC (see Algorithm 1) by inference in polynomial equations. Let $𝒮$ be a SLAC-program solving $\mathrm{CSP}(\mathrm{\Gamma })$. In order to prove Theorem 6 we take an instance $𝒫=(V,U_d,𝒞)$ of $\mathrm{CSP}(\mathrm{\Gamma })$ that has no solution, and therefore is not SLAC-consistent, as $\mathrm{CSP}(\mathrm{\Gamma })$ has bounded width, and prove that it also has no operator solution. We will prove it by contradiction, assuming $𝒫$ has an operator solution $\{A_v\}$ and then using the rules of a SLAC-program solving $\mathrm{CSP}(\mathrm{\Gamma })$ to infer stronger and stronger conditions on $\{A_v\}$ that eventually lead to a contradiction.

Recall that every rule of a SLAC-program has the form $(x\in S)\wedge R(x,y,z_1,\mathrm{\dots },z_r))\to (y\in S^{\prime })$ for some variables $x,y\in V$, a constraint $⟨(x,y,z_1,\mathrm{\dots },z_r),R⟩$, and sets $S,S^{\prime }\subseteq U_d$. Therefore, we need to show how to encode unary relations and rules of a SLAC-program through polynomials. For any $S\subseteq U_d$, the unary constraint restricting the domain of a variable $x$ to the set $S$ is represented by the polynomial

Similarly, the rule $(x\in S)\wedge R(x,y,z_1,\mathrm{\dots },z_r))\to (y\in S^{\prime })$ of the SLAC program is represented by

To give an idea of how Theorem 6 is proved, we sketch the proof of the following.

The second part of our main result boils down to the following.

Assume that $\mathrm{CSP}(\mathrm{\Gamma })$ does not have bounded width. The “implementation” of linear equations in $\mathrm{CSP}(\mathrm{\Gamma })$ that preserves gaps will be achieved in several steps via a chain of reductions that lies at the heart of the algebraic approach to CSPs [12]. The reductions are shown in Figure 1. They are known to preserve satisfiability; we show that they also preserve satisfiability gaps.

The most basic reduction (used in the chain in several places) is that of primitive positive definitions. Let $\mathrm{\Gamma }$ be a constraint language over $U_d$, let $r$ be an integer, and let $x_1,\mathrm{\dots },x_r$ be variables ranging over the domain $U_d$. A primitive positive formula (pp-formula) over $\mathrm{\Gamma }$ is a formula of the form

where $R_i$ is either the binary equality relation on $U_d$ or $R_i\in \mathrm{\Gamma }$ is a relation over $U_d$ of arity $r_i$, and each ${𝐳}_i$ is an $r_i$-tuple of variables from $\{x_1,\mathrm{\dots },x_r\}\cup \{y_1,\mathrm{\dots },y_s\}$. A relation $R\subseteq U_d^r$ is primitive positive definable (pp-definable) from $\mathrm{\Gamma }$ if there exists a pp-formula $\varphi (x_1,\mathrm{\dots },x_r)$ over $\mathrm{\Gamma }$ such that $R$ is equal to the set of models of $\varphi$, that is, the set of $r$-tuples $(a_1,\mathrm{\dots },a_r)\in U_d^r$ that make the formula $\varphi$ true over $U_d$ if $a_i$ is substituted for $x_i$ in $\varphi$ for every $i\in [r]$.

Weaker forms of Theorem 9 have appeared in the literature. This includes for example subdivisions from Theorem 6.4 of [49].

Let $R\subseteq U_d^r$ be a pp-definable formula over $\mathrm{\Gamma }$ via the pp-formula $\varphi (x_1,\mathrm{\dots },x_r)$ as in (4). Given an instance $𝒫\in \mathrm{CSP}(\mathrm{\Gamma }\cup \{R\})$, one can turn it into an instance ${𝒫}^{\prime }\in \mathrm{CSP}(\mathrm{\Gamma })$ that is equivalent to $𝒫$. Intuitively, each constraint $⟨𝐮,R⟩$ of $𝒫$ is replaced with constraints from its pp-definition in (4) over fresh new variables (and similarly for the binary equality relation, cf. [18] for details). This construction is known as the gadget construction in the CSP literature and it is known that $𝒫$ has a solution over $U_d$ if and only if ${𝒫}^{\prime }$ has a solution over $U_d$ [12, 5]. Thus, to prove Theorem 9, it suffices to show the following; the proof is a simple generalization of the $d=2$ case proved in [2].

If $\mathrm{CSP}(\mathrm{\Gamma }\cup \{R\})$ has a satisfiability gap of the first kind then there is an unsatisfiable instance $𝒫\in \mathrm{CSP}(\mathrm{\Gamma }\cup \{R\})$ with a satisfying operator assignment. By [12] (cf. also [5]), ${𝒫}^{\prime }$ is unsatisfiable. By Lemma 10, ${𝒫}^{\prime }$ has a satisfying operator assignment. Hence ${𝒫}^{\prime }$ establishes that $\mathrm{CSP}(\mathrm{\Gamma })$ has a satisfiability gap, and Theorem 9 is proved. This argument also extends to gaps of the second and third kind.

Pp-definitions are the starting point of the algebraic approach to CSPs [12] and suffice for dealing with Boolean CSPs, not only in [2] but also in all papers on Boolean (variants of) CSPs. For CSPs over larger domains, more tools are needed.

A constraint language $\mathrm{\Gamma }$ is a core language if all its endomorphisms are permutations; that is, $\mathrm{\Gamma }$ has no endomorphisms that are not automorphisms. There always exists an endomorphism $\varrho$ of $\mathrm{\Gamma }$ such that $\varrho (\mathrm{\Gamma })$ is core and $\varrho \circ \varrho =\varrho$ [12]. We will denote this core language by $\mathrm{𝖼𝗈𝗋𝖾}(\mathrm{\Gamma })$, as it (up to an isomorphism) does not depend on the choice of $\varrho$.

A constraint language $\mathrm{\Gamma }$ is called idempotent if it contains all the constant relations, that is, relations of the form $C_a=\{(a)\}$, $a\in U_d$. For an arbitrary language $\mathrm{\Gamma }$ over $U_d$ we use ${\mathrm{\Gamma }}^{\ast }=\mathrm{\Gamma }\cup \{C_a\mid a\in U_d\}$. A unary relation (a set) $B\subseteq U_d$ pp-definable in $\mathrm{\Gamma }$ is called a subalgebra of $\mathrm{\Gamma }$. For a subalgebra $B$ we introduce the restriction $\mathrm{\Gamma }\text{<span class="ltx\_rule" style="width:0.4pt;height:10pt;vertical-align:-3.0pt;background:black;display:inline-block;"> </span>}B$ of $\mathrm{\Gamma }$ to $B$ defined as $\mathrm{\Gamma }\text{<span class="ltx\_rule" style="width:0.4pt;height:10pt;vertical-align:-3.0pt;background:black;display:inline-block;"> </span>}B=\{R\cap B^{ar(R)}\mid R\in \mathrm{\Gamma }\}$.

An equivalence relation $\theta$ pp-definable in $\mathrm{\Gamma }$ is said to be a congruence of $\mathrm{\Gamma }$. The equivalence class of $\theta$ containing $a\in U_d$ will be denoted by $a/\theta$, and the set of all equivalence classes, the factor-set, by $U_d/\theta$. Congruences of a constraint language allow one to define a factor-language as follows. For a congruence $\theta$ of the language $\mathrm{\Gamma }$ the factor language $\mathrm{\Gamma }/\theta$ is the language over $U_d/\theta$ given by $\mathrm{\Gamma }/\theta =\{R/\theta \mid R\in \mathrm{\Gamma }\}$, where $R/\theta =\{(a_1/\theta ,\mathrm{\dots },a_n/\theta )\mid (a_1,\mathrm{\dots },a_n)\in R\}$.

All the languages above are related to each other by the reducibility of the corresponding CSPs, as Figure 1 indicates. In the full version [18], we show that all arrows in Figure 1 preserve satisfiability gaps. To relate these reductions with bounded width and magic squares we use the following result.

To prove Theorem 8, suppose that $\mathrm{CSP}(\mathrm{\Gamma })$ does not have bounded width. By Proposition 11 there is a language $\mathrm{\Delta }$ pp-definable in $\mathrm{\Gamma }$, a subalgebra $B$ of $\mathrm{𝖼𝗈𝗋𝖾}{(\mathrm{\Delta })}^{\ast }$, a congruence $\theta$ of $\mathrm{𝖼𝗈𝗋𝖾}{(\mathrm{\Delta })}^{\ast }\text{<span class="ltx\_rule" style="width:0.4pt;height:10pt;vertical-align:-3.0pt;background:black;display:inline-block;"> </span>}B$, and an Abelian group $𝔸$ of prime order $p$ such that ${\mathrm{\Gamma }}^{\prime }=\mathrm{𝖼𝗈𝗋𝖾}{(\mathrm{\Delta })}^{\ast }\text{<span class="ltx\_rule" style="width:0.4pt;height:10pt;vertical-align:-3.0pt;background:black;display:inline-block;"> </span>}B/\theta$ contains relations $R_{3,a},R_{p+2}$ for every $a\in 𝔸$. Our goal is to show that if $\mathrm{CSP}({\mathrm{\Gamma }}^{\prime })$ has a satisfiability gap then so does $\mathrm{CSP}(\mathrm{\Gamma })$.

To give an idea of the gap-preservation proofs, we sketch how a satisfiability gap is preserved. Let $\mathrm{\Gamma }$ be a constraint language over the set $U_d$ and let $B$ be its subalgebra. We show that if $\mathrm{CSP}(\mathrm{\Gamma }\text{<span class="ltx\_rule" style="width:0.4pt;height:10pt;vertical-align:-3.0pt;background:black;display:inline-block;"> </span>}B)$ has a satisfiability gap then so does $\mathrm{CSP}(\mathrm{\Gamma })$. We show this for a gap of the first kind (over finite-dimensional Hilbert spaces); the infinite-dimensional case is more complicated, cf. [18] for details. Let $\mathrm{\Delta }=\mathrm{\Gamma }\text{<span class="ltx\_rule" style="width:0.4pt;height:10pt;vertical-align:-3.0pt;background:black;display:inline-block;"> </span>}B$. Then by Theorem 9 we may assume $\mathrm{\Delta }\subseteq \mathrm{\Gamma }$ and $B\in \mathrm{\Gamma }$. Let $e=|B|$ and $\pi :U_e\to U_d$ a bijection between $U_e$ and $B$. Let $𝒫=(V,U_e,𝒞)$ be a gap instance of $\mathrm{CSP}({\pi }^{-1}(\mathrm{\Delta }))$ and the instance ${𝒫}^{\pi }=(V,U_d,{𝒞}^{\pi })$ constructed as follows: For every $⟨𝐬,R⟩\in 𝒞$ the instance ${𝒫}^{\pi }$ contains $⟨𝐬,\pi (R)⟩$. As is easily seen, ${𝒫}^{\pi }$ has no classic solution. Therefore, it suffices to show that for any satisfying operator assignment $\{A_v\mid v\in V\}$ for $𝒫$, the assignment $C_v=\pi (A_v)$ is a satisfying operator assignment for ${𝒫}^{\pi }$.

By a technical lemma that shows that injective maps on finite sets that are interpolated by polynomials preserve normal operators that pairwise commute [18], the $C_v$’s are normal, satisfy the condition $C_v^d=I$, and locally commute. For $⟨𝐬,R⟩\in 𝒞$, $𝐬=(v_1,\mathrm{\dots },v_k)$, let $f_R^{\pi }(x_1,\mathrm{\dots },x_k)=f_R({\pi }^{-1}(x_1),\mathrm{\dots },{\pi }^{-1}(x_k))$. It can be shown that ${\pi }^{-1}(C_v)=A_v$, and therefore $f_R^{\pi }(C_{v_1},\mathrm{\dots },C_{v_k})=I$. For any $a_1,\mathrm{\dots },a_k\in U_d$, if $(a_1,\mathrm{\dots },a_k)\in \pi (R)$ then $a_1,\mathrm{\dots },a_k\in B$. Therefore, $f_R^{\pi }(a_1,\mathrm{\dots },a_k)=1$ then $f_{\pi (R)}(a_1,\mathrm{\dots },a_k)=1$. By Lemma 5 this implies $f_{\pi (R)}(C_{v_1},\mathrm{\dots },C_{v_k})=I$.

The other reductions use similar ideas, carefully relying on the spectral theorem given in Theorem 3 to simultaneously diagonalize the restriction of an operator assignment to the scope of a constraint, Lemma 5 that relates polynomial equations over $U_d$ and operators, and the above mentioned result on preservation of operator assignments by certain polynomials. The infinite-dimensional case is more delicate, relying on the General Strong Spectral Theorem (Theorem 4).

To finish the proof of Theorem 1, assume that $\mathrm{CSP}(\mathrm{\Gamma })$ does not have bounded width and ${\mathrm{\Gamma }}^{\prime }$ from Proposition 11 is over a group of prime order $p$. As reductions preserve satisfiability gaps, it suffices that $\mathrm{CSP}({\mathrm{\Delta }}_p)$, where ${\mathrm{\Delta }}_p=\{R_{3,a}\mid a\in 𝔸\}\cup \{R_{p+2}\}$, has a satisfiability gap. The result of Slofstra and Zhang [60] provides a gap instance of $\mathrm{CSP}(\{R_{3,1},R_{3,-1}\})$ of the second kind for any prime $p$, and thus the same holds for $\mathrm{CSP}(\mathrm{\Gamma })$. For $p=2$ the Mermin-Peres magic square from [50] provides a gap instance of $\mathrm{CSP}(\{R_{3,1},R_{3,-1}\})$ of the first kind, and same holds for $\mathrm{CSP}(\mathrm{\Gamma })$. Finally, the result by Slofstra [59] provides a gap instance of $\mathrm{CSP}(\{R_{3,1},R_{3,-1}\})$ of the third kind, and we get the same for $\mathrm{CSP}(\mathrm{\Gamma }\cup \{R_T\})$, where $R_T$ is the full binary relation on $U_d$. Finally, if $\mathrm{CSP}(\mathrm{\Gamma })$ is NP-hard then $\mathrm{\Gamma }$ can simulate any constraint language [12], and thus in particular ${\mathrm{\Delta }}_2$.