2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 16 at 5:32
  • $\begingroup$ Thank you, Apass.Jack and Yuval Filmus. Much appreciated. $\endgroup$ – Jason T. Feb 16 at 5:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.