Suppose someone has developed a $poly(n,d)$-time algorithm $A(x)$ for the problem and we know this $poly(n,d)$, which is equal to some $p(n,d)$. Because for the minimal DFA that accepts all strings $d=1$, then the running time of the algorithm A is equal to some polynomial $q(n)$ if the given NFA is universal. If the given NFA is not universal than we just let A make $q(n)$ steps and terminate it if it hasn't terminated: either we found the DFA and can check directly or terminated and we know that the resulting DFA cannot be universal.

Thank you, this paper really gives the answer. In fact, it seems that the main result was obtained by Alon and Friedland in this paper: emis.ams.org/journals/EJC/Volume_15/PDF/v15i1n13.pdf. There they show that graphs which are union of complete bipartite graphs have the maximum number of perfect matchings among all graphs with the same degree sequence.

It can probably help somebody to answer you question if you give a link to the proof of #P-completeness for general case.

This is surely equivalent to maximum-clique, because you should just construct a graph, in which vertices correspond to $N(a)$ for each $a$ and connect two vertices with an edge iff the corresponding subsets intersect. Now you need to solve maximum-clique in the complement graph.