Consider the problem of reasoning about the identity of a set from the size of its intersections with other sets. you are given a finite set u of size n, and a collection a1, . . , am of subsets of u. you are also given numbers c1, . . , cm. the question is:
1. does there exist a set x ⊂ u so that for each i = 1, 2, . . , m, the cardinality of x ∩ ai is equal to ci?
we will call this an instance of the intersection inference problem, with input u, {ai}, and {ci}.
2. prove that intersection inference is np-complete.