# Hardness of problem related to number of subsets that satisfy a particular property

I have the following algorithmic problem. I am given a set of elements. Each element has a set of properties. For example:

A: has properties p1, p2, p4
B: has properties p2, p4
C: has properties p2, p1


The task is to find the number of subsets of elements, where the union of the properties of the elements in the subset are equal to some predefined set.

For example if the predefined set is:

• {p2}, then the answer is 0, because there are no subsets with a union of {p2}
• {p1, p2, p4}, then the answer is 5, because we can take {A}, {A, B}, {A, C}, {B, C}, {A, B, C}

This problem seems like it might be hard (e.g., NP-hard), but I can not find anything similar in this list of NP-complete problems. I do realize that this is only small subset of NP complete problems.

Is there an efficient algorithm for this problem? Or, is it NP-hard, and if so, how can we prove that?

• It's not clear that the decision version of this problem is even in NP. – Yuval Filmus Jul 9 '15 at 23:31
• @YuvalFilmus yes, when I meant that I think it is NP, I was thinking about a decision version (is the answer 5?). And I am not sure whether it is NP or not. – randomizer Jul 10 '15 at 1:34
• I agree with Yuval. It's still not clear whether the decision version is in NP. What's the witness/certificate that a specific instance is a "Yes" instance? The obvious candidate is to list all of the subsets that meet the condition, but this won't work if the number 5 is expressed in the input in binary: in general the length of a list of length $k$ will be exponential in the number of bits needed to represent $k$. – D.W. Jul 10 '15 at 1:40
• Sets that are not subsets of the predefined set can't be used, since unions with such sets can't be subsets of the predefined set. ​ If the predefined set is not a subset of the union of the other sets, then the answer would be 0, since the predefined set also couldn't be a subset of the union of any number of the other inputs sets. ​ Thus, one may restrict to the case in which the predefined set is the union of the other input sets. ​ ​ ​ – user12859 Jul 10 '15 at 2:55

Here is the reduction from #Monotone-SAT. Suppose we have a CNF formula $\varphi$ over $n$ variables and with $m$ clauses, where all of the literals in each clause are positive (i.e., no variable is negated). Then we can define an instance of your problem that corresponds to $\varphi$. The problem instance has $n$ elements, one element for each variable, and $m$ properties, one property for each clause. The set of properties of a variable is just the set of clauses that mention that variable. Then the number of solutions to this problem instance is exactly the number of satisfying assignments to $\varphi$.