New answers tagged

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