I have the following #P-complete problem:Given an alphabet $\Sigma$ and a matrix $M$ where each entry can be a symbol from $\Sigma$ or the wildcard symbol $*$, find the number of strings $s$ with the property that there exists $i$ such that for all $j$, $M_{i,j} \neq *$ implies $s_j = M_{i,j}$.Example:If $\Sigma = \{a,b,c\}$ and $M$ = $$\left(\begin{matrix}a&*&b \\ *&c&* \end{matrix} \right)$$then there are three satisfying strings: $aab,abb,acb$.I was told this can be solved using BDDs, somehow, such that a lot of caching is possible. How does that work? Also, what are other algorithms for this?Proof of #P-completeness:We reduce from #UNSAT, the problem of counting the number of unsatisfying assignments for a boolean formula. Given a formula $\varphi$ with $n$ variables and $m$ clauses, make an $m$ by $n$ matrix $M$ over the alphabet $\Sigma = \{0,1\}$ such that$$M_{i,j} = \begin{cases}1\text{ if the $j^{th}$ literal is unnegated in the $i^{th}$ clause,} \\0\text{ if the $j^{th}$ literal is negated in the $i^{th}$ clause,} \\*\text{ otherwise.}\end{cases}$$Then the number of strings with the above property equals the number of unsatisfying assignments for $\varphi$.
Counting words that satisfy SAT-like constraints with BDDs
algorithms;combinatorics;counting;bdd