# Complexity/Hardness of a generalization of an Inclusion/Exclusion problem

I would appreciate some help in determining the complexity/hardness of an inclusion/exclusion problem described in Wikipedia: https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle#A_generalization

Namely, given a family of subsets $$A_1$$, $$A_2$$, ..., $$A_n$$ of a universal set $$S$$, I need to calculate the number of elements of $$S$$ which appear in exactly some fixed $$m$$ of these sets.

Would that be #P?

Thank you.

For each element in $$S$$, count the number of times it is a member of $$A_i$$, $$1\le i\le n$$. If that number is $$m$$, we add 1 to the tally. The final tally is what we wanted.
The above algorithm takes $$O(tn)$$ time if the computational cost to check membership is $$O(1)$$. It takes $$O(ttn)$$ time if the computational cost to check membership proportional to the size of the set, which is at most $$t$$.
So you can see the problem is in $$P$$. It has nothing to do with that general inclusion–exclusion principle.
• You can improve the running time to $O(\sum_i |A_i|)$ by only going over the elements in the $A_i$, using a hash table. Alternatively, losing a log factor, you can just sort the concatenated sets. – Yuval Filmus Feb 16 '19 at 5:32