World's most popular travel blog for travel bloggers.

Upper bounding randomized k-SAT solver

, , No Comments
Problem Detail: 


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(\mathit{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.

Asked By : ddnomad
Answered By : Yuval Filmus

Hint: Use a union bound.

Note that for $m \geq 2^k$ you cannot provide any non-trivial bound, since there are formulas with $2^k$ clauses of width $k$ that are unsatisfiable. The same example shows that the bounded hinted above is tight (for all $m \leq 2^k$).

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback