<p>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.</p>

<p>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} &amp;\equiv&amp; \neg{a} \wedge (b \vee \neg{b}) \wedge (c \vee \neg{c}) \\
&amp;\equiv&amp; (\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}) \\
&amp;\equiv&amp; \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\}$.</p>

CC BY-SA 3.0
2011-12-27T20:41:27.283Z
Thanks a lot for the systematic approach. Now I can get bounds for two variables, etc.
Matt Groff
CC BY-SA 3.0
2011-12-30T05:39:56.247Z
@mjqxxxx Awesome answer.
Tayfun Pay
CC BY-SA 3.0
2012-11-04T22:01:28.300Z
@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.
Matt Groff
CC BY-SA 3.0
2013-03-07T18:39:40.873Z
@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).
mjqxxxx
CC BY-SA 3.0
2013-03-08T20:25:17.263Z
@mjqxxxx:  It seems to me that clause counting isn't worthwhile.  I've put some of my findings in an answer.
Matt Groff
CC BY-SA 3.0
2011-12-27T19:04:55.877Z
2011-12-27T19:04:55.877Z
mjqxxxx
<p>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.</p>

<p>For 4-SAT, the situation is similar.  Consider the set of clauses:</p>

<p>$$(\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)$$</p>

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

CC BY-SA 3.0
2013-03-08T20:24:23.987Z
2013-03-08T20:24:23.987Z
Matt Groff
<p>MAX3E SAT is defined as SAT with all clauses consisting of 3 literals and their possible negations.  We define <em>clause counting</em>, 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.</p>

<p>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?</p>

CC BY-SA 3.0
2011-12-26T16:48:43.250Z
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?
Matt Groff
CC BY-SA 3.0
2011-12-26T18:19:07.050Z
This may be a naïve question, but are there restrictions on the clause construction? or are the clauses of arbitrary form and length?
Ahmed Masud
CC BY-SA 3.0
2011-12-26T20:23:01.887Z
All clauses are of length 3 - 3 literals per clause.  Other than that, there are no restrictions.
Matt Groff
CC BY-SA 3.0
2011-12-27T00:42:39.127Z
I assume clauses are in CNF?
Ahmed Masud
CC BY-SA 3.0
2011-12-27T02:33:04.070Z
All clauses are in CNF.
Matt Groff
CC BY-SA 3.0
2011-12-27T05:00:43.750Z
Do you already know of a counter example of any size?
Tyson Williams
CC BY-SA 3.0
2011-12-27T12:04:55.593Z
@Tyson Williams:  No.  I have tried to find one, but no luck yet.
Matt Groff
<cc.complexity-theory><sat>
The worst-case scenario(s) for MAX3E SAT
Matt Groff
# The worst-case scenario(s) for MAX3E SAT

(Asked by: username_0 on 2011-12-26)

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?

**Tags:** cc.complexity-theory, sat
> **Comments:**
> **username_0**: 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?  
> **username_1**: This may be a naïve question, but are there restrictions on the clause construction? or are the clauses of arbitrary form and length?  
> **username_0**: All clauses are of length 3 - 3 literals per clause.  Other than that, there are no restrictions.  
> **username_1**: I assume clauses are in CNF?  
> **username_0**: All clauses are in CNF.  
> **username_2**: Do you already know of a counter example of any size?  
> **username_0**: @Tyson Williams:  No.  I have tried to find one, but no luck yet.  

---

## 2 answers

### Answer by username_3 on 2011-12-27. Score: 6 | Accepted answer

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\}$.

> **Comments:**
> **username_0**: Thanks a lot for the systematic approach. Now I can get bounds for two variables, etc.  
> **username_4**: @mjqxxxx Awesome answer.  
> **username_0**: @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.  
> **username_3**: @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).  
> **username_0**: @mjqxxxx:  It seems to me that clause counting isn't worthwhile.  I've put some of my findings in an answer.  

---

### Answer by username_0 on 2013-03-08. Score: 4

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...


---

