6
$\begingroup$

Let $S_1,\dots,S_n$ be variables representing unknown sets. A set expression has the form $S_i$, $\overline{E}$ (the complement of $E$), or $E \cap E'$, where $E,E'$ are set expressions. A constraint has the form $E = \emptyset$ or $E \ne \emptyset$, where $E$ is a set expression. Given a conjunction of constraints, the problem is to determine whether they are satisfiable, i.e., whether there is an assignment from variables to sets that makes all of the constraints hold.

Conjecture: if there exists a satisfying assignment, then there is a satisfying assignment where all sets are subsets of a universe $U$ with $k$ elements, where $k$ is the number of constraints of the form $E \ne \emptyset$.

Is this conjecture true?

I suspect it is, but I can't seem to prove it. I can prove it if there is no complement operator, but my proof strategy seems to go awry if there are complements. (Proof strategy: suppose the constraints are $E_1 \ne \emptyset$, .., $E_k \ne \emptyset$, and suppose we have any satisfying assignment. Let $x$ be the smallest element of $E_1 \cup \dots \cup E_k$, where $x$ is an element of $E_i$; then add $x$ to $U$, discard $E_i$, and repeat. Once this is finished, replacing each set $S_i$ with $S_i \cap U$ still leaves all constraints satisfied.) If this conjecture is true, it is a sort of "small-world theorem", which says that a not-too-large universe suffices for checking satisfiability. These kinds of theorems are helpful for improving the performance of constraint-solving algorithms.

$\endgroup$
2
$\begingroup$

The conjecture is true, and the proof strategy listed there can be made to work.

Let $s = (s_1,\dots,s_n)$ be a satisfying assignment for the variables that makes all of the constraints hold. We'll write $E(s)$ for the result of evaluating the expression $E$ with the variables $S_i$ set to $s_i$. In the following, define $U$ by the procedure listed in the question: let $E_1 \ne \emptyset$, ..., $E_k \ne \emptyset$ be the constraints of second type; pick any element of $E_1(s) \cup \cdots \cup E_k(s)$, call it $x$; add $x$ to $U$; delete all of the constraints $E_i \ne \emptyset$ such that $x \in E_i$; and repeat. Define $s'_i = s_i \cap U$.

Now I claim that $s'_1,\dots,s'_n$ is also a satisfying assignment that makes all of the constraints hold.

First, let's consider the constraints of the form $E = \emptyset$. I claim that if $E(s) = \emptyset$, then $E(s') = \emptyset$. In particular, I claim that $E(s) \cap U = E(s') \cap U$ for all set expressions $E$. The proof is by recursion: by definition of $s'$, we have $S_i(s) \cap U = S_i(s') \cap U$; also if $t \cap U = t' \cap U$, then $\overline{t} \cap U = \overline{t'} \cap U$; and if $t_1 \cap U = t'_1 \cap U$ and $t_2 \cap U = t'_2 \cap U$, then $(t_1 \cap t_2) \cap U = (t'_1 \cap t'_2) \cap U$. So this means that $s'$ satisfies all of the constraints of the first type (all of the constraints of the form $E = \emptyset$), since $s$ does.

Next, consider the constraints of the form $E \ne \emptyset$. We know $E(s) \ne \emptyset$. Therefore, there was a step in the iterative definition of $U$ when we chose some element $x \in E(s)$ and added it to $U$. We proved earlier that $E(s) \cap U = E(s') \cap U$. Since $x \in E(s)$ and $x \in U$, it follows that $x \in E(s') \cap U$, and thus $E(s') \ne \emptyset$. This means that $s'$ satisfies all of the constraints of the second type, too.

We've shown that if there is any satisfying assignment for all constraints, then there exists a satisfying assignment where all sets are subsets of $U$. This completes the proof of the conjecture.

$\endgroup$
  • 1
    $\begingroup$ A good question. But you should hide the spoiler just in case someone else wants to solve it (him/her)self. :) $\endgroup$ – fade2black Jul 11 '17 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.