1
$\begingroup$

$\phi$ is a 3SAT CNF formula. All variables in each clause of $\phi$ are distinct. The expected number of satisfied clauses under the uniform random assignment is given as $\frac{7m}{8}$. A satisfying assignment of the CNF means that all $m$ clauses must be true. (A CNF is defined as a conjunction of disjunction of literals.)

We know that if $m < 8$, then that means $E(X) < 7$. I don't understand how this suggests the existence of at least one satisfying assignment.

Hints will be appreciated, thank you!

$\endgroup$
0
$\begingroup$

The idea here is that if there are no satisfying assignments then $X$ can never be more than $m-1,$ and so we must have $E(X)\leq m-1$. When is that true?

$\endgroup$
3
  • $\begingroup$ When all the variables $x_1, x_2, x_3$ repeat themselves in all clauses? $\endgroup$ – user445310 Apr 19 '18 at 12:04
  • $\begingroup$ @user445310 you know $E(X)=7m/8$, so when is that $\leq m-1$? $\endgroup$ – Especially Lime Apr 19 '18 at 12:24
  • $\begingroup$ When $m \leq 8$? $\endgroup$ – user445310 Apr 19 '18 at 12:47
0
$\begingroup$

HINT

The hardest version of a $7$ clause 3SAT problem would be when all clauses refer to the same $3$ variables. Now, with $3$ variables, how many possible truth-assignments are there?

$\endgroup$
3
  • $\begingroup$ $\frac{1}{8}$ ? $\endgroup$ – user445310 Apr 19 '18 at 12:02
  • $\begingroup$ I meant 8 possible assignments as $2^3$. $\endgroup$ – user445310 Apr 19 '18 at 12:55
  • $\begingroup$ @user445310 exactly. Now make a connection between those 7 clauses and the 8 truth-assignments ... if I have a specific clause, how many out of those 8 truth-assignments satify it? $\endgroup$ – Bram28 Apr 19 '18 at 14:46

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.