# Satisfiable CNFs where each clause contains logarithmically many different literals

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)$$?
• What's $|\varphi|$? Is it the number of clauses ("verses" in you question)? Jul 16 '21 at 14:06
• 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). Jul 16 '21 at 15:27

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

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.