3
$\begingroup$

I am looking for a solver that computes an approximation to #SAT. In other words, given a formula $\phi(x)$ in CNF, approximately count the number of satisfying assignments to $\phi$. I'm interested in an approximate count, not the exact number. Are there any existing working implementations that I can download and try?

To be clear, I'm not looking for algorithms or for papers describing algorithms; I'm looking for an implementation I can use, in the style of a SAT solver. This question is related to #SAT Solver download, except that one asks for solvers that exactly count the number of satisfying assignments, whereas I am interested in solvers that approximate the number of satisfying assignments (I do not need an exact count).

$\endgroup$
2
$\begingroup$

Ashish Sabharwal lists some software (e.g., SampleCount, ApproxCount, and more) for this on his web page. I haven't tried any of these.

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