2
$\begingroup$

Studying for my finals in Complexity theory. This question comes up in different variants and it requires to use probability.

A side note before, to be more clear: A CNF clause consists of $n$ clauses $C_i$, so $\varphi=C_1\wedge\dots \wedge C_n$, and each $C_i$ has some amount of literals $l_1^i,\ldots ,l_m^i$, so $C_i=l_1^i\vee\dots \vee l_m^i$, and each $l_i$ is some variable $x$ or its negation $\lnot x$.

Let $L$ consist of all satisfiable CNFs $\varphi$ such that each clause of $\varphi$ contains at least $\log_{2}\left(|\varphi|\right)$ different literals.

Prove that $L\in P$.

I know that we could write a Turing machine $M$ on $\langle \varphi\rangle$ go over each clause in $\varphi$ and count the number of literals. If it's less than $\log_2\left(|\varphi|\right)$ then reject. Otherwise accept. Of course this machine is polynomial. But we need to prove: $L(M)=L$.

Over the course, they showed a way to use probability. A similar question was given:

Given a 3CNF clause $\varphi$ in which every clause consists of different variables, at least $\frac{7}{8}$ of the clauses can be satisfied simultaneously.

This idea was used to prove that the language $L'$ of all $\varphi\in 3SAT$ in which each clause contains different variables such that there exist an assignment that satisfies $7/8$ of the clauses is in $P$.

So I tried to prove my main task and I would love some feedback.

We want to calculate the probability of $\varphi\in CNF$ so each clause in it, contains exactly $\log_{2}\left(|\varphi|\right)$ literals, to be satisfied.

We will define a probability space where each assignment for $\varphi$'s variables is selected with a uniform probability. For each clause $C_k$ we will define the following indicator: $$ \mathbb{I}_{k}\triangleq\begin{cases} 1 & z\left(C_{k}\right)=T\\ 0 & \text{otherwise} \end{cases} $$ So we get: $$ E\left(\mathbb{I}_{k}\right)=0\cdot P\left(\mathbb{I}_{k}=0\right)+1\cdot P\left(\mathbb{I}_{k}=1\right)=P\left(\mathbb{I}_{k}=1\right) $$ Let's calculate the probability of $P\left(\mathbb{I}_{k}=1\right)$. Let's look at $C_{k}=\left(l_{1}^{k}\vee\ldots\vee l_{\log_{2}\left(|\varphi|\right)}^{k}\right)$ where all the literals are independent and we will calculate the probability of $z$ being $z\left(C_{k}\right)=T$.

Let's define $\Omega$ to be all the possibilities. So we get $|\Omega|=2^{\log_{2}\left(|\varphi|\right)}=|\varphi|$ (since the literals are independent).

Let's define $A$ to be all the possibilities so we get true. This means that at least one of the literals should return true. So we get $|A|=|\varphi|-1$.

Since this is an equal probability space we will get: $$ P\left(A\right)=\frac{|A|}{|\Omega|}=\frac{|\varphi|-1}{|\varphi|} $$

Now we get $P\left(A\right)\leq P\left(\mathbb{I}_{k}=1\right)$ (since literals are not necessarily independent). Then we get: $$ E\left(\mathbb{I}_{k}\right)=P\left(\mathbb{I}_{k}=1\right)\geq\frac{|\varphi|-1}{|\varphi|} $$ Lets mark $t$ to be the number of clauses in $\varphi$. Also, lets mark $X=\sum_{k=1}^{t}\mathbb{I}_{k}$ So we get: $$ E\left(X\right)=E\left(\sum_{k=1}^{t}\mathbb{I}_{k}\right)=\sum_{k=1}^{t}E\left(\mathbb{I}_{k}\right)\geq\sum_{k=1}^{t}\frac{|\varphi|-1}{|\varphi|}=\frac{|\varphi|-1}{|\varphi|}t=t\cdot\left(1-\frac{1}{|\varphi|}\right) $$

From this we can conclude that there is necessarily an assignment that satisfies $t$ clauses from $\varphi$ and therefore it satisfies $\varphi$, i.e. $\varphi \in SAT$.

Since this question comes very often in the finals, I want to make sure I understand each step. So the things I'm not sure about:

  1. I'm not sure that my statement of $P\left(A\right)\leq P\left(\mathbb{I}_{k}=1\right)$ is being true. I'm not sure how to calculate the probability if the literals are not independent. From the question, they should be different, but I could have $x$ and $\lnot x$ in the same clause, and they are of course dependent.
  2. The question asks about "at least $\log_{2}\left(|\varphi|\right)$" and I talked about "exactly $\log_{2}\left(|\varphi|\right)$".
  3. What do I actually get out of proving that $E\left(X\right)\geq t\cdot\left(1-\frac{1}{|\varphi|}\right)$?
$\endgroup$
2
  • 1
    $\begingroup$ What's $|\varphi|$? Is it the number of clauses ("verses" in you question)? $\endgroup$
    – Steven
    Jul 16 '21 at 14:06
  • $\begingroup$ 1. If a clause $C$ contains both $x$ and $\overline{x}$, then $C$ is trivially true and you can just ignore it. 2. Your lower bound on $\Pr(\mathbb{I}_k)$ still holds. Let $x<y$ and assume that no clause contains both a variable and its negation. The probability that a random assignment satisfies a clause with $x$ literals is smaller than the probability that it satisfies a clause with $y$ literals. 3. You can conclude that there must be a truth assignment that satisfies at least $|\varphi| (1-1/|\varphi|) = |\varphi|-1$ clauses. This is not enough to prove the claim (see my answer). $\endgroup$
    – Steven
    Jul 16 '21 at 15:27
2
$\begingroup$

The claim is false.

Let $\varphi = (x_1 \vee x_2) \wedge (\overline{x}_1 \vee x_2) \wedge (x_1 \vee \overline{x}_2) \wedge (\overline{x}_1 \vee \overline{x}_2)$. Here $|\varphi|=4$, each clause in $\varphi$ contains exactly $\log_2 |\varphi|=2$ distinct literals, yet $\varphi$ is not satisfiable. (This is also a counterexample if $|\varphi|$ denotes the number of variables).

You have an error in your proof when you observe that $$ \mathbb{E}[X] \ge |\varphi| \cdot \left(1-\frac{1}{|\varphi|}\right) = |\varphi|-1, $$ and use it to conclude that there must be a truth assignment that satisfies all the $|\varphi|$ clauses. You can only conclude that there must be a truth assignment that satisfies $|\varphi|-1$ clauses (you are using the fact that $\max \{y_1, \dots, y_k\} \ge \frac{1}{k} \sum_{i=1}^k y_k$, this is false in general if $\ge$ is replaced with $>$).

$\endgroup$
2
$\begingroup$

You haven't explained what $|\varphi|$ is, so let's guess that it is the number of clauses. So you are given a CNF $C_1 \land \cdots \land C_n$ in which each clause contains at least $\log_2 n$ distinct literals.

Any clause which contains both a variable and its negation is always satisfied, so we can remove such clauses; call them spurious. Suppose that the remaining clauses are $C_1,\ldots,C_m$, where $m \leq n$.

If you choose a random truth assignment, then the probability that it falsifies a non-spurious clause containing $k$ different literals is exactly $2^{-k}$. This means that a random truth assignment falsifies each of $C_1,\ldots,C_m$ with probability at most $2^{-\log_2 n} = 1/n$, and applying a union bound, this shows that the probability that a random truth assignment falsifies at least one of $C_1,\ldots,C_m$ is at most $m/n$. If $m < n$, this means that the CNF is satisfiable, since a random truth assignment satisfies it with positive probability.

If $m = n$ then this argument no longer works, and indeed you can construct counterexamples, such as: $$ x_1 \land \lnot x_1 \\(x_1 \lor x_2) \land (\lnot x_1 \lor x_2) \land (x_1 \lor \lnot x_2) \land (\lnot x_1 \lor \lnot x_2) $$

First of all, let us note that if any of the clauses $C_1,\ldots,C_n$ contains more than $\log_2 n$ variables, then the argument above does show that a random truth assignment satisfies the CNF with positive probability. Hence $k = \log_2 n$ must be an integer, and each clause contains exactly $k$ literals. Thus the probability that a random truth assignment falsifies each of $C_1,\ldots,C_n$ is exactly $1/n$, and so the expected number of falsified clauses is exactly $1$.

Since the expected number of falsified clauses is exactly $1$, the CNF is unsatisfiable iff every truth assignment falsifies at most one clause. Equivalently, the CNF is unsatisfiable iff every two clauses $C_i,C_j$ cannot be falsified simultaneously. A short argument reveals that the latter condition holds precisely when there is some literal $\ell \in C_i$ such that $\lnot \ell \in C_j$, a condition which is easily checked.

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