3-SAT and Partition Lattices
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.
An older post
This post is from an earlier period of work and has not been revised since it was written. It is here because it still stands, not because it is current: names, links and affiliations are as they were at the time.
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,
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.