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

CC BY-SA 4.0
2023-11-07T12:58:47.280Z
2023-11-07T12:58:47.280Z
Laakeri
<p>Say we have <span class="math-container">$n$</span> sets <span class="math-container">$A_1,\dots,A_n$</span> with elements from a universal set <span class="math-container">$U$</span>.</p>
<p>We want to compute the cardinality of <span class="math-container">$\cup_{i=1}^n 2^{A_i}$</span> or at least decide on non-trivial bounds. Is this problem NP-complete?</p>
<p>The obvious counting algorithm is <span class="math-container">$\mathcal{O}(n 2^m)$</span> where <span class="math-container">$m = \max_i |A_i| \leq |U|$</span>.</p>
<p>I tried using the principle of inclusion-exclusion since intersections of power sets has nicer behavior. This gives <span class="math-container">$\mathcal{O}(2^n m)$</span> 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.</p>
<p>In the special case where our set-system is a sunflower with core <span class="math-container">$|Y| = k$</span>, then <span class="math-container">$|\cup_{i=1}^n 2^{A_i}| = \sum_{i=1}^n 2^{|A_i|} - (n - 1) 2^k$</span>. 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.</p>

CC BY-SA 4.0
2022-01-30T19:39:04.110Z
It is #P-complete. There is a reduction from counting vertex covers.
Laakeri
CC BY-SA 4.0
2022-01-30T22:19:38.043Z
@Laakeri Can you elaborate on the reduction?
Joseph Mckinsey
CC BY-SA 4.0
2022-02-07T21:50:26.030Z
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.
Neal Young
<cc.complexity-theory><np-hardness><set-system>
Is counting the union of power sets NP-complete?
Joseph Mckinsey
# Is counting the union of power sets NP-complete?

(Asked by: username_0 on 2022-01-30)

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.

**Tags:** cc.complexity-theory, np-hardness, set-system

> **Comments:**
> **username_1**: It is #P-complete. There is a reduction from counting vertex covers.  
> **username_0**: @username_1 Can you elaborate on the reduction?  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_1 on 2023-11-07. Score: 2

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\}}$.


---

