4

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).

Community
  • 1
D.W.
  • 12,054
  • 2
  • 34
  • 80

1 Answers1

2

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

D.W.
  • 12,054
  • 2
  • 34
  • 80