3
$\begingroup$

For a given MAXSAT problem, it is trivially easy to compute the mean number of clauses satisfied for all assignments, or equivalently the expected number of clauses satisfied by a random assignment.

Is it likewise possible to compute the variance of the number of clauses satisfied? And I mean an exact computation, not an estimate.

In general, which moments are easy to compute, and which are hard?

I would prefer an answer for general MAXSAT but would also be interested in the special case of MAX-3-SAT.

$\endgroup$
  • $\begingroup$ All constant moments, at the very least, should be easy to compute. It’s an exercise. $\endgroup$ – Yuval Filmus Nov 14 '18 at 1:07
  • $\begingroup$ What do you mean by "constant" moments? $\endgroup$ – Mike Battaglia Nov 14 '18 at 1:14
  • $\begingroup$ I accidentally assumed that the MAXSAT instance is also chosen at random. When the instance is fixed and has size $m$, then you should be able to compute $\mathbb{E}[\binom{X}{d}]$, where $X$ is the number of satisfied clauses under a random assignment, in time $O(m^d)$. It's still an exercise. $\endgroup$ – Yuval Filmus Nov 14 '18 at 1:19
2
$\begingroup$

Suppose that the MAXSAT instance consists of clauses $C_1,\ldots,C_m$. Denote by $X$ the expected number of clauses satisfied by a random assignment. Then $$ \mathbb{E}\left[\binom{X}{d}\right] = \sum_{\substack{S \subseteq [m] \\ |S|=d}} \Pr[C_i \text{ is satisfied for all } i \in S]. $$ This gives a roughly $O(m^d)$ algorithm for computing the $d$th moment.

$\endgroup$

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.