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.