patternMinor
Variance of MAXSAT clause satisfiability
Viewed 0 times
clausesatisfiabilityvariancemaxsat
Problem
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.
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.
Solution
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.
$$
\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.
Context
StackExchange Computer Science Q#100046, answer score: 2
Revisions (0)
No revisions yet.