<p>If the SAT instance has a unique solution then you are asking for the actual solution. Given the Valiant&ndash;Vazirani randomized reduction from SAT to unique SAT, if there was a way of efficiently estimating the probability distribution of variables then you could use it to solve SAT.</p>

CC BY-SA 3.0
2014-10-15T22:42:38.287Z
2014-10-15T22:42:38.287Z
Yuval Filmus
<p>Consider that we have a state space of n random variables, for simplicity, the variable value can be 0 or 1. Each variable has its probability distribution when it is not constrained, also for simplicity, it can be a uniform distribution (50% probability for 0 and 50% for 1). And there is a set of constraints over the variables, thus in the constrained state space, the actual probability distribution of each variable will skewed. For example, if we have two variables a,b and a constraint a=0->b=1, the actually probability that b=0 will be 1/3 compared to 0.5 when unconstrained.</p>

<p>I am wondering if there are any results on estimating the probability distribution of the random variables under a set of constraints. The golden answer of the probability distribution could be derived by using the SAT solver to get all the solutions and then computing the statistics, which is prohibitively computationally expensive. Thus I am wondering if there is any way to do a fair estimation on that.</p>

<csp>
How to estimate the probability of distribution of a variable in a Constraint Satisfication Problem
Wen
# How to estimate the probability of distribution of a variable in a Constraint Satisfication Problem

(Asked by: username_0 on 2014-10-15)

Consider that we have a state space of n random variables, for simplicity, the variable value can be 0 or 1. Each variable has its probability distribution when it is not constrained, also for simplicity, it can be a uniform distribution (50% probability for 0 and 50% for 1). And there is a set of constraints over the variables, thus in the constrained state space, the actual probability distribution of each variable will skewed. For example, if we have two variables a,b and a constraint a=0->b=1, the actually probability that b=0 will be 1/3 compared to 0.5 when unconstrained.

I am wondering if there are any results on estimating the probability distribution of the random variables under a set of constraints. The golden answer of the probability distribution could be derived by using the SAT solver to get all the solutions and then computing the statistics, which is prohibitively computationally expensive. Thus I am wondering if there is any way to do a fair estimation on that.

**Tags:** csp


---

## 1 answers

### Answer by username_1 on 2014-10-15. Score: 2

If the SAT instance has a unique solution then you are asking for the actual solution. Given the Valiant–Vazirani randomized reduction from SAT to unique SAT, if there was a way of efficiently estimating the probability distribution of variables then you could use it to solve SAT.


---

