Is counting the union of power sets NP-complete?

Say we have $$n$$ sets $$A_1,\dots,A_n$$ with elements from a universal set $$U$$.

We want to compute the cardinality of $$\cup_{i=1}^n 2^{A_i}$$ or at least decide on non-trivial bounds. Is this problem NP-complete?

The obvious counting algorithm is $$\mathcal{O}(n 2^m)$$ where $$m = \max_i |A_i| \leq |U|$$.

I tried using the principle of inclusion-exclusion since intersections of power sets has nicer behavior. This gives $$\mathcal{O}(2^n m)$$ solution. I suspect there might be a nice reduction from set-cover or by recasting the sets and elements as vertices in a bipartite graph, but I haven't had any luck.

In the special case where our set-system is a sunflower with core $$|Y| = k$$, then $$|\cup_{i=1}^n 2^{A_i}| = \sum_{i=1}^n 2^{|A_i|} - (n - 1) 2^k$$. I thought that maybe the sunflower lemma could reduce the problem to a smaller size, but I can't see how to create a new problem by taking out a sunflower.

• It is #P-complete. There is a reduction from counting vertex covers. Commented Jan 30, 2022 at 19:39
• @Laakeri Can you elaborate on the reduction? Commented Jan 30, 2022 at 22:19
• In the case when each element in $U$ is in at most $d=O(1)$ sets, I guess inclusion-exclusion gives you an $O(n^d)$-time algorithm. Commented Feb 7, 2022 at 21:50

It is $$\#P$$-complete. Here is a reduction from counting vertex covers. Let $$G = (V,E)$$. We wish to count the number of sets of vertices that are not vertex covers. We observe a set $$X \subseteq V$$ is not a vertex cover if and only if there exists an edge $$uv \in E$$ so that $$X \subseteq V \setminus \{u,v\}$$. Now, we have that the family of all sets of vertices that are not vertex covers is equal to $$\bigcup_{uv \in E} 2^{V \setminus \{u,v\}}$$.