3-SAT and partition lattices

Reading time: about 4 minutes (853 words).

It is not hard to see that 3-SAT reduces to the problem of deciding whether all coatoms in a certain partition lattice are contained in the union of a collection of certain principal filters. Therefore, the latter problem, which we will call the covered coatoms problem (CCP), is NP-complete. In this post we simply define CCP. Later we check that 3-SAT reduces to CCP, and then develop some ideas about constructing a feasible algorithm to solve CCP.

Consider the relational structure $\mathbf B = \langle \{0, 1\}, R\rangle$ where $R$ is the ternary relation $\{0, 1\}^3 - \{(0,0,0), (1,1,1)\}$. That is,

$$ R = {(0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0)}.$$

We now describe the constraint satisfaction problem $\operatorname{CSP}(\mathbf B)$.

By an "instance" of $\operatorname{CSP}(\mathbf B)$, we mean a (finite) relational structure $\mathbf A = \langle A, S \rangle$ with a single ternary relation $S$.

The constraint satisfaction problem $\operatorname{CSP}(\mathbf B)$ is the following:

Given an instance $\mathbf A = \langle A, S \rangle$, does there exist a relational homomorphism from $\mathbf A$ to $\mathbf B$? That is, does there exist a function $f: A \rightarrow \{0,1\}$ such that $(f(a), f(b), f(c)) \in R$ whenever $(a, b, c) \in S$?

The kernel of a function $f$ with codomain $\{0,1\}$ has two equivalence classes, or "blocks"---namely, $f^{-1}\{0\}$ and $f^{-1}\{1\}$.

If one of these classes is empty, then $f$ is constant in which case it cannot be a homomorphism into the relational structure $\langle \{0, 1\}, R\rangle$ (since $(0,0,0)\notin R$ and $(1,1,1)\notin R$).

Therefore, the kernel of every homomorphism $f : \mathbf A \rightarrow \mathbf B$ has two nonempty blocks.

Now, given a partition of $A$ into two blocks, $\pi = |A_1|A_2|$, there are exactly two functions of type $A \rightarrow \{0,1\}$ with kernel $\pi$. One is $f(x) = 0$ iff $x \in A_1$ and the other is $1-f$. It is obvious that either both $f$ and $1-f$ are homomorphisms or neither $f$ nor $1-f$ is a homomorphism.

Indeed, both are homomorphisms if and only if for all tuples $(a,b,c) \in S$ we have $\{a,b,c\} \nsubseteq A_1$ and $\{a,b,c\} \nsubseteq A_2$.

Neither is a homomorphism if and only if there exists $(a,b,c) \in S$ with $\{a,b,c\} \subseteq A_1$ or $\{a,b,c\} \subseteq A_2$.

Now, for each tuple $s = (a,b,c) \in S$, we let $\langle s\rangle$ denote the equivalence relation of $A$ generated by $a$, $b$, and $c$.

It is clear that a function $f: A \rightarrow \\{0, 1\\}$ is a homomorphism from $\mathbf A$ to $\mathbf B$ if and only if for all $s \in S$ the relation $\langle s\rangle$ does not belong to the kernel of $f$. Therefore, a solution to the instance $\mathbf A = \langle A, S \rangle$ of $\operatorname{CSP}(\mathbf B)$ exists if and only if there is at least one coatom in the lattice of equivalence relations of $A$ that is not contained in the union $ \bigcup_{s\in S} \, ^\uparrow\langle s \rangle $ of principal filters.

The Covered Coatoms Problem is the following: Given a set $A$ and a list $s_1 = (a_1, b_1, c_1), s_2=(a_2, b_2, c_2), \dots, s_n =(a_n, b_n, c_n)$ of 3-tuples with elements drawn from $A$, decide whether all of the coatoms of the lattice $\prod_A$ of partitions of $A$ are contained in the union $ \bigcup_{i=1}^n , ^\uparrow\langle s_i \rangle $ of principal filters.

If we find an algorithm that decides this in polynomial time (in the size of the set $A$), or if we prove that no such algorithm exists, then this would answer the P versus NP question.