patternMinor
Satisfiable CNFs where each clause contains logarithmically many different literals
Viewed 0 times
literalssatisfiableeachlogarithmicallywherecnfsdifferentcontainsmanyclause
Problem
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\rig
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\rig
Solution
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 $>$).
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 $>$).
Context
StackExchange Computer Science Q#142342, answer score: 3
Revisions (0)
No revisions yet.