6
$\begingroup$

MAX3E SAT is defined as SAT with all clauses consisting of 3 literals and their possible negations. We define clause counting, for this question, as the ability to count the total number of satisfied clauses for all remaining possible truth assignments. Let's say that we are allowed to pick a single variable and assign it a value, and then perform clause counting to get a total for all remaining possible truth assignments. Further, we can do this for all variables and their negations.

Let's consider this clause counting ability for MAX3E SAT with an equation that is garaunteed to be satisfiable by at least one possible truth assignment. Now, the clause counting from above can be used to help predict part of a satisfying truth assignment. The variable we pick with the highest clause count should (probably) be part of a satisfying truth assignment. I'd like to construct the smallest example (in terms of clauses) where this notion of clause counting fails. Can someone please help?

$\endgroup$
  • $\begingroup$ I am also interested in the case where we extend the clause counting capabilities to pick two variables. What is the smallest example where two variables won't allow us to pick part of a satisfying variable assignment? $\endgroup$ – Matt Groff Dec 26 '11 at 16:48
  • $\begingroup$ This may be a naïve question, but are there restrictions on the clause construction? or are the clauses of arbitrary form and length? $\endgroup$ – Ahmed Masud Dec 26 '11 at 18:19
  • $\begingroup$ All clauses are of length 3 - 3 literals per clause. Other than that, there are no restrictions. $\endgroup$ – Matt Groff Dec 26 '11 at 20:23
  • $\begingroup$ I assume clauses are in CNF? $\endgroup$ – Ahmed Masud Dec 27 '11 at 0:42
  • $\begingroup$ All clauses are in CNF. $\endgroup$ – Matt Groff Dec 27 '11 at 2:33
6
$\begingroup$

In fact, we are able to perform "clause counting". The total number of satisfied clauses for all remaining truth assignments is proportional to the expected number of satisfied clauses for a random truth assignment, which is the sum of the probabilities $P(C_i | \{x, y, ...\})$, where $C_i$ is the $i$-th clause, and $\{x,y,...\}$ are the literals that have been assigned to be true. In particular, if there are three distinct literals per clause, and we are promised a satisfying truth assignment (so a variable and its negation never occur in the same clause), and a single literal $x$ has been assigned to be true, then the probability that a particular clause is satisfied by a random assignment of the remaining variables is $3/4$ if the clause contains $\neg{x}$, or $7/8$ if the clause contains neither $x$ nor $\neg{x}$, or $1$ if the clause contains ${x}$. That is, $$P(C_i | \{x\}) = \frac{7}{8} + \frac{1}{8}n_i(x),$$ where $n_i(x) \in\{-1, 0,1\}$. So the literal picked out by "clause counting" will be the one that maximizes $\sum_{i}n_i(x)=N(x)$, where the sum is over all clauses, and $N(x)$ is the (net) number of occurrences of the literal $x$ in the entire formula.

To use this to construct a counterexample, we need a literal that is false (say) in all satisfying assignments, but that maximizes the above count. We can force a literal to be false with four occurrences of its negation, as follows: $$ \begin{eqnarray} \neg{a} &\equiv& \neg{a} \wedge (b \vee \neg{b}) \wedge (c \vee \neg{c}) \\ &\equiv& (\neg{a} \vee b \vee c) \wedge (\neg{a} \vee b \vee \neg{c}) \wedge (\neg{a} \vee \neg{b} \vee c) \wedge (\neg{a} \vee \neg{b} \vee \neg{c}) \\ &\equiv& \Phi(\neg{a};b,c), \end{eqnarray} $$ for any additional literals $b$ and $c$; this subformula has $N(a)=-4$ and $N(b)=N(c)=0$. We then need to include enough occurrences of $a$ in the rest of the formula to make $N(a)$ the largest count. This can be done using $$ \Omega(a;d,f) \equiv (a \vee d \vee f) \wedge (a \vee d \vee \neg{f}) \wedge (a \vee \neg{d} \vee f), $$ which is equivalent to $a \vee (d \wedge f)$, and has $N(a)=3$ and $N(d)=N(f)=1$. So a counterexample with four variables and ten (unique) clauses is $$ \Phi(\neg{a}; x_1, x_2) \wedge \Omega(a; x_1, x_3) \wedge \Omega(a; x_2, x_3), $$ which has $N(a)=2$ and $N(x_1)=N(x_2)=N(x_3)=1$, and a unique satisfying assignment: $\{\neg{a}, x_1, x_2, x_3\}$.

$\endgroup$
  • $\begingroup$ Thanks a lot for the systematic approach. Now I can get bounds for two variables, etc. $\endgroup$ – Matt Groff Dec 27 '11 at 20:41
  • $\begingroup$ @mjqxxxx Awesome answer. $\endgroup$ – Tayfun Pay Dec 30 '11 at 5:39
  • $\begingroup$ @mjqxxxx: Isn't $N(x_3)=2$? Sorry, I don't mean to nitpick, but I recently have been investigating this question again. Your counterexample is still fine for what I'm using it for. $\endgroup$ – Matt Groff Nov 4 '12 at 22:01
  • 1
    $\begingroup$ @MattGroff: You're right; it does have $N(x_3)=2$, and so $a$ and $x_3$ are tied for the largest count. If you add another term, $\Omega(a;x_1,x_2)$, to the conjunction, then $N(a)=5$ and $N(x_1)=N(x_2)=N(x_3)=2$, and there's still the same unique satisfying assignment (with $a$ false). $\endgroup$ – mjqxxxx Mar 7 '13 at 18:39
  • $\begingroup$ @mjqxxxx: It seems to me that clause counting isn't worthwhile. I've put some of my findings in an answer. $\endgroup$ – Matt Groff Mar 8 '13 at 20:25
4
$\begingroup$

I've found that we can construct a 5 clause example where clause counting fails. Consider the clauses: $$(\neg a_1 \lor \neg a_2 \lor b)$$ $$(\neg a_1 \lor \neg a_2 \lor \neg b)$$ $$(a_1 \lor a_2 \lor b)$$ $$(a_1 \lor a_2 \lor c)$$ $$(a_1 \lor a_2 \lor d)$$ Here $$(\neg a_1 \lor \neg a_2 \lor b \lor c \lor d)$$ satisfies. However, clause counting fails to predict this using a single variable as a pick. Multiple variables (i.e. combinations of variables as picks) are needed to get the correct result. I've found this to be inefficient, though, compared to existing methods.

For 4-SAT, the situation is similar. Consider the set of clauses:

$$(\neg a_1 \lor \neg a_2 \lor b \lor c) \land (\neg a_1 \lor \neg a_2 \lor \neg b \lor c)\land (\neg a_1 \lor \neg a_2 \lor b \lor \neg c) \land (\neg a_1 \lor \neg a_2 \lor \neg b \lor \neg c) \land$$ $$(a_1 \lor a_2 \lor b \lor c) \land (a_1 \lor a_2 \lor \neg b \lor c) \land (a_1 \lor a_2 \lor b \lor \neg c) \land$$ $$(a_1 \lor a_2 \lor d \lor c) \land (a_1 \lor a_2 \lor \neg d \lor c) \land (a_1 \lor a_2 \lor d \lor \neg c)$$

Clause counting fails here for 4-SAT, 6 variables, and 10 clauses. It seems that clause counting isn't worthwhile...

$\endgroup$

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.