Approximating $1$-In-$3$ SAT by Linearly Ordered Hypergraph $3$-Colouring Is NP-Hard

Classifying the complexity of PCSPs is a very active area of research (see, e.g. survey [30]). We will give a brief overview that focuses solely on the results that are closely related to approximating 1-in-3 SAT and to the topological method in PCSP.

Approximating 1-in-3 SAT by NAE was one of the first known tractable non-trivial approximation of a $\mathrm{𝖭𝖯}$-hard CSP by another [12]. More specifically, one algorithm works as follows: given a satisfiable instance of 1-in-3 SAT, one relaxes each constraint in it (say on variables $x,y,z$) to a linear equation $x+y+z=1$ over the integers. One then solves the obtained linear system over integers (which can be done in polynomial time [28]), and rounds the obtained solution by mapping positive integers to 1 and non-positive ones to 0. It is easy to see that this rounding sends any triple of integers such that $x+y+z=1$ to a triple of Boolean values that cannot be constant, thus providing a NAE solution for the original instance. This polynomial-time algorithm is a special case of the basic AIP (affine integer programming) algorithm, whose applicability for PCSPs was characterised in [6]. The Approximate 1-in-3 Sat conjecture predicts that every approximation of 1-in-3 SAT either can be solved by the above algorithm with appropriately chosen rounding, or it remains $\mathrm{𝖭𝖯}$-hard (see Section 2.1 for a formal statement). This conjecture was confirmed in [18] for approximations by so-called rainbow-free relations (in which no tuple has three pairwise different elements). The conjecture was also confirmed in [5] for relations on the set $\{0,1,2\}$, with a single exception that the authors were not able to classify.

This unclassified case from [5] is related to a variant of the colouring problem for hypergraphs called linearly ordered (LO) colouring [5, 40] (also known as the unique maximum colouring [17]). This variant assumes that the set of colours is linearly ordered, e.g. equal to $\{0,1,\mathrm{\dots },k-1\}$. A LO $k$-colouring of a hypergraph is an assignment of the colours to the vertices of a hypergraph so that, for each hyperedge $e$, if colour $c$ is the largest colour that appears in it, then $c$ is assigned to exactly one vertex in $e$. For example, in a LO 3-colouring, for a hyperedge $(x,y,z)$, the colours $(0,1,2)$ or $(0,2,0)$ would be acceptable, but not $(0,1,1)$. Observe that the LO 2-colouring problem for 3-uniform hypergraph is precisely 1-in-3-SAT. Analogously to the approximate graph colouring problem, the approximate LO hypergraph colouring problem is defined [5] as follows, for fixed constants $2\le k\le \mathrm{\ell }$:

Given a 3-uniform hypergraph that is promised to have a LO $k$-colouring, find a LO $\mathrm{\ell }$-colouring for it.

It was conjectured in [5] that this problem is $\mathrm{𝖭𝖯}$-hard for all constants $2\le k\le \mathrm{\ell }$. The case $k=2,\mathrm{\ell }=3$ of this problem was exactly the only unclassified approximation of 1-in-3 SAT by a relation on $\{0,1,2\}$. Up to now, this conjecture was confirmed only in the following cases. It was observed [23] that, for $4\le k\le \mathrm{\ell }$, there is a very easy reduction to the approximate LO colouring problems with constants $k,\mathrm{\ell }$ from the approximate graph colouring problem with constants $k-1,\mathrm{\ell }-1$. Hence, any known results about approximate graph colouring translate in this way to results about this conjecture. Apart from this, the only confirmed $\mathrm{𝖭𝖯}$-hardness case for approximate LO colouring is for $k=3,\mathrm{\ell }=4$ [23], with a proof based on topological combinatorics. LO hypergraph colouring can naturally be defined not only for 3-uniform hypergraphs, but for $r$-uniform hypergraph with $r\ge 3$. The approximate LO colouring problem is known to be $\mathrm{𝖭𝖯}$-hard for all $3\le k\le \mathrm{\ell }$ and $r\ge 4$ and for $k=2$ and all $r\ge \mathrm{\ell }+2$ (see [39, 40]). The best known efficient algorithm to find a LO $\mathrm{\ell }$-colouring for a LO $2$-colourable $3$-uniform hypergraph with $n$ vertices uses $\mathrm{\ell }\approx \log n$ colours [10, 27]. The problem of finding a LO $3$-colouring for a given LO $2$-colourable 3-uniform hypergarphs (which is the same as the problem of approximating 1-in-3-SAT by LO 3-colourings) was specifically mentioned in [5, 18, 23, 40, 39] as an open question and an obstacle for further progress in classifying the approximate 1-in-3 SAT problems.

We denote the problem of finding a LO $3$-colouring for a given LO $2$-colourable $3$-uniform hypergraph by $\mathrm{PCSP}({\mathrm{𝐋𝐎}}_2,{\mathrm{𝐋𝐎}}_3)$ – the notation will be explained in Section 2.1. In this paper, our main result settles its complexity.

Combined with the partial classification obtained in [5], Theorem 1 implies a complete dichotomy for approximations of 1-in-3 SAT by $3$-element structures.

We remark that the confirmed case $k=3,\mathrm{\ell }=4$ of the LO colouring conjecture that we mentioned above easily follows from Theorem 1 (see Section 4), thus providing a more elementary proof of the main result in [23].

The proof of Theorem 1 is a combination of a structural result (Theorem 23) followed by a direct application of a well-known sufficient condition for $\mathrm{𝖭𝖯}$-hardness of a PCSP [7, 13]. Theorem 23 states, roughly, that the polymorphisms of $\mathrm{PCSP}({\mathrm{𝐋𝐎}}_2,{\mathrm{𝐋𝐎}}_3)$ exhibit two kinds of behaviour - precisely the two kinds that are characteristic for the two flavours of applications of topology in PCSPs that we described above. Even though our proof is combinatorial, it shows that our problem is the first example where the features behind the two uses of topology in PCSP appear together. Thus, it is likely to be very useful in guiding further development of the topological method in Promise CSP. It is important to note that whilst some of the applications of topology lead to alternative proofs of known results, e.g. [37, 39], or to a modest step forward in comparison with existing results, e.g. [3, 23], their methodological contribution is highly meaningful. The classification of PCSPs is still in its infancy and requires a more diverse toolbox than for CSPs. The development of new methods or the identification of issues that said methods must be able to deal with are highly sought after by current research directions [30].

A relational structure is a tuple $𝐀=(A;R_1,\mathrm{\dots },R_m)$ where $A$ is a set referred to as the domain of $𝐀$, and each $R_i$ is a relation on $A$ of arity ${\mathrm{ar}}_i\ge 1$; that is, $R_i\subseteq A^{{\mathrm{ar}}_i}$. In this paper we will only consider structures with a single symmetric binary relation (undirected graphs) or with a single ternary symmetric relation (i.e. invariant under permutations of coordinates), which we refer to as $3$-uniform hypergraphs by slightly abusing standard terminology.

Relational structures $𝐀=(A;R_1,\mathrm{\dots },R_m)$ and $𝐁=(B;R_1^{\prime },\mathrm{\dots },R_{m^{\prime }}^{\prime })$ are said to be similar if $m=m^{\prime }$ and the relations $R_i$ and $R_i^{\prime }$ have same arity for each $i\in \left[m\right].$ For similar relational structures $𝐀,𝐁$ as above, a mapping $f:A\to B$ is said to be a homomorphism if for all $i\in \left[m\right]$ we have $x\in R_i⟹f\left(x\right)\in R_i^{\prime }$, where $f$ is applied component-wise to $x$. We write $f:𝐀\to 𝐁$ to indicate that $f$ is a homomorphism, and use the notation $𝐀\to 𝐁$ to indicate that a homomorphism from $𝐀$ to $𝐁$ exists.

Every PCSP template $(𝐀,𝐁)$ defines a decision problem and a search problem as follows. The decision version of $\mathrm{PCSP}(𝐀,𝐁)$ asks to decide, for a given input structure $𝐗$ similar to $𝐀$ and $𝐁$, whether $𝐗\to 𝐀$ or whether $𝐗\to ̸𝐁$, the promise being that exactly one of these cases occurs. The search version of $\mathrm{PCSP}(𝐀,𝐁)$ asks, given an input structure $𝐗$ with a promise that $𝐗\to 𝐀$, to find a homomorphism $f:𝐗\to 𝐁$. The decision version trivially reduces to the search version, but it is not known whether the two versions are always polynomial-time equivalent (see [34] for recent results on this question). Hardness results are typically, and in this paper (cf. Theorems 1 and 13), proven for the decision version, and hence apply to the search version as well. Observe that if $𝐀=𝐁$, then $\mathrm{PCSP}(𝐀,𝐁)$ is the same as the standard $\mathrm{CSP}\left(𝐀\right)$; that is, the problem of deciding whether $𝐗\to 𝐀$. The PCSP framework allows a systematic study of problems that cannot be expressed as CSPs, and can be thought of as “qualitative” approximations of CSPs. Below are some examples of PCSPs relevant for this paper - more can be found in [1, 2, 5, 11, 21, 23, 25, 30, 39, 40].

All known tractable cases of $\mathrm{PCSP}({\mathrm{𝐋𝐎}}_2,𝐁)$ can be solved by essentially the same algorithm as the one for $\mathrm{PCSP}({\mathrm{𝐋𝐎}}_2,{𝐇}_2)$ that we described in Section 1.1. Consider the (infinite) structure $𝐙=(\mathbb{Z};\{(x,y,z)\mid x+y+z=1\})$. Trivially, we have ${\mathrm{𝐋𝐎}}_2\to 𝐙$ by inclusion. Assume that we additionally have $𝐙\to 𝐁$. Then the search version (and therefore the decision version as well) of $\mathrm{PCSP}({\mathrm{𝐋𝐎}}_2,𝐁)$ can be solved in polynomial time by reducing it to solving a system of linear equations over $\mathbb{Z}$. Indeed, for an input $𝐗$ such that $𝐗\to {\mathrm{𝐋𝐎}}_2$, we have $𝐗\to 𝐙$ because homomorphisms compose. Finding a homomorphism from $𝐗$ to $𝐙$ amounts to solving a system of linear equations over integers (which can done in polynomial time [28]). By composing the found homomorphism from $𝐗$ to $𝐙$ with the assumed homomorphism from $𝐙$ to $𝐁$, we can find the required homomorphism from $𝐗$ to $𝐁$. (There is a potential issue that all homomorphisms from $𝐙$ to $𝐁$ may be not computable, which can happen in a similar context in PCSPs [34], but has not occurred so far in Approximate 1-in-3 SAT). Now we can formally state the Approximate 1-in-3 SAT conjecture that we mentioned several times before.

As explained above, this conjecture has been confirmed in several special cases [5, 18]. It is easy to verify that $𝐙\to ̸{\mathrm{𝐋𝐎}}_k$ for any $k\ge 2$, so that, indeed, $\mathrm{PCSP}({\mathrm{𝐋𝐎}}_2,{\mathrm{𝐋𝐎}}_k)$ stands on the hardness side of the approximate 1-in-3 SAT conjecture. The simple reasoning, which can be found, e.g., in (the proof of) Proposition 8 in [18] and which we now sketch, implies the following necessary condition for $𝐙\to 𝐁$. Let $D(𝐁)$ be the digraph whose vertices are the elements of $B$ and edges are all pairs $(x,y)$ such that $(x,x,y)$ is in the relation of $𝐁$. Assume that there is a homomorphism $𝐙\to 𝐁$. Consider all triples of the form $(a,a,1-2a)$ from $𝐙$, and their images in $𝐁$ under the assumed homomorphism. These images show that the digraph $D(𝐁)$ must contain a homomorphic image of an infinite directed path, which always contains a directed cycle or a loop, since $B$ is finite. It is easy to see that $D({\mathrm{𝐋𝐎}}_k)$ is a transitive tournament, so it contains neither a directed cycle nor a loop, and it follows that $𝐙\to ̸{\mathrm{𝐋𝐎}}_k$. We remark that the structures ${\mathrm{𝐋𝐎}}_k$ are the richest structures $𝐁$ with the property that $D(𝐁)$ contains neither a directed cycle nor a loop - it is not hard to see that any ($k$-element) structure with this property is isomorphic to a substructure of ${\mathrm{𝐋𝐎}}_k$.

Polymorphisms are “higher order” homomorphisms that determine the complexity of CSPs and PCSPs. The body of work concerned with the use of polymorphisms for deriving reductions between PCSPs is generally referred to as the algebraic theory of PCSPs, the core of which can be found in [6, 12]. In this section we review some basic notions.

If $(𝐀,𝐁)$ is any PCSP template and $\phi :𝐀\to 𝐁$, then it is easy to see that, for all $n\ge 1$ and $i\in \left[n\right]$, all functions of the form $f(x_1,\mathrm{\dots },x_n)=\phi (x_i)$ are polymorphisms of $(𝐀,𝐁)$. In the special case when $A\subseteq B$ and $\phi$ is the inclusion map, such polymorphisms are called projections (also known as dictators).

The polymorphisms of a structure $𝐀$ are closed under composition; hence the success of applications of universal algebra in the classification of CSPs. This is not the case for PCSPs: indeed, for a general template, composition of polymorphisms is not well defined. Instead, we work with a “composition free” structure where the functions are closed under permuting the variables, identifying them or adding dummy ones. Formally, we refer to these operations as taking a minor.

It follows immediately from the definitions that, for any PCSP template $(𝐀,𝐁)$, the set of all polymorphisms of $(𝐀,𝐁)$ is a minion. It is denoted by $\mathrm{Pol}(𝐀,𝐁)$.

There are several polymorphism-based sufficient conditions for $\mathrm{𝖭𝖯}$-hardness of PCSPs (see, e.g., [4, 6, 7, 13, 30]). We will use the following one in the proof of Theorem 1. A chain of minors in $\mathrm{Pol}(𝐀,𝐁)$ is a sequence $(f_1,{\pi }_{1,2},f_2,\mathrm{\dots },f_{l-1},{\pi }_{l-1,l},f_l)$ where $f_i\in \mathrm{Pol}(𝐀,𝐁)$ for each $i\in \left[l\right]$ and $f_i^{{\pi }_{i,i+1}}=f_{i+1}$.

The above theorem was first proved in [13] by using the PCP theorem and the NP-hardness of (layered) Gap Label Cover problem. It was later shown in [7] that the $\mathrm{𝖭𝖯}$-hardness in fact follows by a direct and simple “bounded width” reduction from 1-in-3 SAT (or from any $\mathrm{𝖭𝖯}$-hard CSP).

We use the notion of an $i$-set as in [5] to describe the action of a polymorphism of $({\mathrm{𝐋𝐎}}_2,{\mathrm{𝐋𝐎}}_3)$. Fix some $n$ and consider a function $f:{\{0,1\}}^n\to \{0,1,2\}$. We can identify tuples from ${\{0,1\}}^n$ with subsets from $[n]$, where a subset $X$ corresponds to the tuple having 1 exactly in positions in $X$. Then notation $f(X)$ has the obvious meaning. We say that $X\subseteq \left[n\right]$ is an $i$-set of $f$ for some $i\in \{0,1,2\}$ if $f(X)=i$. It is easy to see that if $g=f^{\pi }$ and $X$ is an $i$-set of $g$ then ${\pi }^{-1}(X)$ is an $i$-set of $f$. If $f(X)\in \{0,1\}$ then we call $X$ a boolean set of $f$, and we say that a 2-set of $f$ small if it contains three elements or less.

It is straightforward to check that a function $f:{\{0,1\}}^n\to \{0,1,2\}$ is a polymorphism of $({\mathrm{𝐋𝐎}}_2,{\mathrm{𝐋𝐎}}_3)$ if, and only if, for all partitions $(X,Y,Z)$ of $\left[n\right]$ into three subsets (some of which may be empty), we have that $(f\left(X\right),f\left(Y\right),f\left(Z\right))\in {\mathrm{LO}}_3$. Observe that the empty set can never be a 2-set. We say that a partition $(X,Y,Z)$ of $\left[n\right]$ is a boolean partition (for $f$) if $\{f\left(X\right),f\left(Y\right),f\left(Z\right)\}=\{0,1\}$. In the language of $i$-sets, the $n$-ary projections of $({\mathrm{𝐋𝐎}}_2,{\mathrm{𝐋𝐎}}_3)$ are the mappings for which there exists some $t\in \left[n\right]$, such that $X\subseteq \left[n\right]$ is a $1$-set if, and only if, $t\in X$ and it is a $0$-set otherwise.

When we use the above terminology ($i$-set, boolean partition etc.) and $f$ is clear from the context, we will omit a reference to it. This should cause no confusion.

Let us informally describe our result about the structure of $\mathrm{Pol}({\mathrm{𝐋𝐎}}_2,{\mathrm{𝐋𝐎}}_3)$ by means of the so-called reconfiguration graph. For $n\ge 1$, consider a graph $G_n$ whose vertices are the $n$-ary polymorphisms of $({\mathrm{𝐋𝐎}}_2,{\mathrm{𝐋𝐎}}_3)$ and there is an edge between two polymorphisms if they differ (as functions) in a single position. Our structural result (Theorem 23) claims, intuitively, that if all polymorphisms with small $2$-sets are removed from $G_n$, then the resulting graph is disconnected, and each of its connected components contains a unique $n$-ary projection. For our hardness result, we will need a more precise and technical version of this statement. It will follow from it that, in fact, each of these connected components has a very structured path from any function to the corresponding unique projection.

The $n$-ary polymorphisms of $({\mathrm{𝐋𝐎}}_2,{\mathrm{𝐋𝐎}}_3)$ can be understood as colourings of the subsets of $\left[n\right]$ using the colour set $\{0,1,2\}$ and subject to the constraints enforced by ${\mathrm{𝐋𝐎}}_3$. We say that a set $X\subseteq \left[n\right]$ is recolourable for a $n$-ary polymorphism $f$ if one can change the image of $X$ to a different value to obtain a mapping that is still a polymorphism of $({\mathrm{𝐋𝐎}}_2,{\mathrm{𝐋𝐎}}_3)$. Specifically, we say that $X$ is recolourable to $i$ or $i$-recolourable for some $i\ne f\left(X\right)$ if the mapping $f^{\prime }$ defined as

is a polymorphism of $({\mathrm{𝐋𝐎}}_2,{\mathrm{𝐋𝐎}}_3)$. We say that a boolean set is static (for $f$) if it is not recolourable to its opposite boolean value. That is, if it is an $i$-set for $i\in \{0,1\}$ and it is not $\left(1-i\right)$-recolourable. The following lemma is straightforward.

Recolouring is a central notion to our structural result: what we show is in fact, that polymorphisms of $({\mathrm{𝐋𝐎}}_2,{\mathrm{𝐋𝐎}}_3)$ without small $2$-sets are essentially projections modulo some recolouring.

The intuition behind this notion is that there is a simple recolouring (path in the graph $G_n$) from $f$ to the corresponding projection: first one recolours all boolean non-static sets $S$ to the value $[t\in S]$ (this can be done in any order), and then one recolours each 2-set $S^{\prime }$ of $f$ to $[t\in S^{\prime }]$ (which can also be done in any order).

It is easy to characterise all $2$-recolourable boolean sets. The following is straightforward.

The above lemma states that the 2-sets of any polymorphism form an intersecting family (i.e. a family of pairwise intersecting subsets of a set), which is an object much studied in extremal combinatorics, see, e.g. [22]. We say that a $n$-ary polymorphism $f$ is upwards closed if for every $2$-set $X$, we have that $X\subseteq Y$ implies $f\left(Y\right)=2$. If $f$ is upwards closed and is such that the complement of every boolean set is a $2$-set (that is, for every $X\subseteq \left[n\right]$ either $X$ or $\overline{X}$ is a $2$-set), we say that $f$ is saturated. Note that in a saturated polymorphism no boolean set is $2$-recolourable, so the $2$-sets of a saturated polymorphism of arity $n$ form a maximal intersecting family of subsets, as studied in [38].

When using the fact that a polymorphism $f$ is saturated in a proof, we may say “by saturation” as a shorthand for “because $f$ is saturated” when $f$ is clear from the context. The following lemma implies that every polymorphism can be recoloured to one that is upwards closed.