4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\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.