1
$\begingroup$

There are $m$ clauses containing a conjunction of 3 variables out of $n$ Boolean variables. (they are of the form $x_i$ $\wedge$ $x_j$ $\wedge$ $x_k$, where each $x_{i,j,k}$ is a variable or it's negation. For these $n$ variables, show that there is an assignment for $x_1,x_2,\cdots,x_n$ that satisfies at least $c*m$ clauses, for some constant $c > 0$. Indicate the value of $c$.

I am confused how to approach with this problem. A clause will be satisfied if all the variables are set to 1. This event happens with probability $\frac{1}{8}$, if we define a random variable $X_i$ which takes a value $1$ when clause $i$ is satisfied and $0$ otherwise. We can show in expectation for a random variable $X = X_1 + X_2 + \cdots + X_m$, but I am unsure that the value of $c$ we are looking for will be $\frac{1}{8}$

what am I missing? Any help is appreciated.

Thanks.

$\endgroup$
0
$\begingroup$

HINT

First, you shouldn't think about this in terms of probability: you need to find a $c$ so that you are certain to have that fraction of clauses satisfiable.

Second, we can easily find an upper bound to $c$ as follows. Imagine you have exactly $8$ clauses, representing all possible combinations of taking exactly $3$ variables and setting them to true of false. It is clear that in that case you can set at most one of the clauses to be true. So, we know for a fact that the upper bound of $c$ is $\frac{1}{8}$: there are cases where you can at most set $\frac{1}{8}$ of the clauses to true.

OK, but is that really the worst case scenario, i.e. Can we always make at least $\frac{1}{8}$ of the clauses true? And how do we prove that? I'll leave you to think about that some more. But again, you should not do this in terms of probability.

$\endgroup$
  • $\begingroup$ I understand what you are saying about proving the upper bound in this case. But, not thinking in terms of probability is a little bit confusing. In a randomized setup, it is intuitive to think about the probability with which the clauses are satisfied. I was thinking, if we are talking about a lower bound, do we have to consider that we can arrange the clauses in $\binom{n}{3}$ ways and $\frac{1}{8}$ for each ? It'd be great if you can help. $\endgroup$ – PeaceFrog Dec 10 '17 at 22:43
  • $\begingroup$ @Peacefrog Think of a truth-table for this: Each of the $m$ clauses will be true in exactly $\frac{1}{8}$ of the $2^n$ rows (posssible assingments) of the table, for a total of $m\cdot \frac{1}{8}\cdot 2^n$ True's. So, if for every assignment there would be less than $\frac{1}{8}$ of the clauses True, you would have a problem, because then the number of True's would add up to less than $2^n \cdot \frac{1}{8} \cdot m$. So, there must be at least one assignment that sets at least $\frac{1}{8}$ of the clauses to True. And so the lower bound for $c$ is $\frac{1}{8}$. $\endgroup$ – Bram28 Dec 11 '17 at 14:12

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.