3
$\begingroup$

Admittedly, homework.

For the purpose of this question: $\phi$ is a DNF formula similar to this one: $(x_1 \wedge \neg x_3 \wedge x_4) \vee (\neg x_1 \wedge x_2)$ Also $C_i$ is a clause in this formula, for example $C_1=x_1\wedge \neg x_3\wedge x_4$

The tasks is to do this in a little bit more sophisticated way than to choose a random assignment, see if it satisfies the formula, repeat N times. More specifically the tasks tells us to:

  • Uniformly at random choose a clause $C_i$ in $\phi$.
  • Set the values of the variables in $C_i$ so that $C_i$ is satisfied.
  • Set the values of the remaining variables randomly.
  • In this way sample only satisfying assignments and sample all of them.

I fail to understand: ALL OF THEM? If I want to sample ALL satisfying assignments then I'm not sampling, but rather I'm counting?

Further the task asks:

  • For a given assignment $p_i$ what is the probability of sampling $p_i$? That's an easy question: $\frac1{2^{n-m}}$ where $n$ is the number or distinct variables in $\phi$ and $m$ is the number of variables in $C_i$. Or am I wrong?
  • How you can use the result of the previous question (the previous question was to sample trivially as I described above) to construct an estimate for the number of satisfying assignments? I don't know.

Well, I can check if this random assignment satisfies any other clauses than $C_i$. But how can I use the result?

My Googling yielded this page: http://theoryapp.com/dnf-counting-and-the-monte-carlo-method/ But this is even more confusing for me. Instead of choosing the clause $C_i$ uniformly, the site tells us to "pick up a clause $C_i$ with probability $P_i=\frac{\left|S_i\right|}{\sum_{j=1}{l}\left|S_j\right|}$, where $S_i$ is the collection of assignments satisfying $C_i$ and $l$ is the amount of clauses in $\phi$ and then pick up an assignment from $S_i$." But then we are told to "Check whether this assignment satisfies $\phi$. Finally, count the number of satisfying samples; denote the count by $M$". This is nonsense, each assignment that satisfies clause $C_i$ for any $i$ must necessary satisfy the whole formula?

Admittedly, this basic course on probability and statistics is the first course where I feel like a total idiot.

Any tips? I'm loosing hopes to be able to figure this out on my own.

Finally, I'm not sure, is this question more appropriate on scicomp.stackexchange.com?

Improve this question
$\endgroup$
1
  • $\begingroup$ The question would be less appropriate on Computational Science, since this is not about scientific computing. It would be more appropriate on your professor's e-mail. $\endgroup$ Commented Dec 13, 2017 at 20:19

1 Answer 1

Reset to default
2
$\begingroup$

Let $\alpha$ be a satisfying assignment. Suppose that it satisfies the terms $\{C_j : j \in J\}$. If you choose $C_i$ in the first step, then the probability that you choose $\alpha$ in the third step is 0 if $i \notin J$ and $2^{-(n-|C_j|)}$ if $i \in J$. Hence the probability of sampling $\alpha$, assuming there are $m$ terms, is $$ p(\alpha) = \frac{2^{-n}}{m} \sum_{j\colon \alpha \text{ satisfies } C_j} 2^{|C_j|}. $$ Let $A$ be a random satisfying assignment chosen according to the algorithm, and let $X = 1/p(A)$. Then $$ E[X] = \sum_{\alpha \text{ satisfying}} \frac{\Pr[A=\alpha]}{p(\alpha)} = \sum_{\alpha \text{ satisfying}} = \text{# satisfying assignments}. $$

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.