New answers tagged co.combinatorics
3
This is #P hard via counting solution to monotone DNF formula.
Let $\phi(x_1,...x_n)$ be monotone DNF formula on $n$ variables.
We are trying to find regular language $L$ over alphabet $\{0,1\}$
with all words of length $n$ and the words in $L$ are in one
to one correspondence with the satisfying assignment of $\phi$.
Variable $x_i$ in $\phi$ corresponds to $...
Top 50 recent answers are included
