0
$\begingroup$

Problem:

Consider a k-SAT solver that assigns values independently uniformly at random to all the variables. Given the formula has $m$ clauses provide an upper bound for the probability of a random assignment to be unsatisfiable.


The issue is that I have no clue from where to start. Both Markov, Chernoff, Chebyshev and McDiarmid's inequalities seem to be not applicable in this situation as the probability of a particular clause to be unsatisfiable depends on the probability of other clauses with overlapping variables to be unsatisfiable.

For every clause the probability of it to be unsatisfiable is $${1 \over {2^k}}$$

There are $m$ clauses in total, so if there are all independent, the answer would be $$P(assignment~is~unsatisfiable) = (2^{-k})^m$$

If somebody would help me a bit with at least some kind of hint I would be extremely grateful.

$\endgroup$
1
$\begingroup$

It always helps in these sorts of problems to determine your distribution and the event that you are working with. By definition of the algorithm, you are taking probabilities over the uniform distribution over all possible assignments. You are trying to find the probability of the event that at least one of the $m$ clauses (call these $C_1, \dots, C_m)$ in the given formula is not satisfied. i.e. $$ \Pr\left(\bigvee_{i = 1}^m \text{$C_i$ is not satisfied}\right). $$ Now you are on the right track. In probability theory, we have ways of giving upper bounds on the disjunction of events, even if they are not independent. (HINT. Treat them like they are independent) (FURTHER HINT. union bound).

$\endgroup$
  • $\begingroup$ Thank you a lot! Every time I do this kind of tasks I forget about union bound. $\endgroup$ – ddnomad Dec 4 '16 at 20:41

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.