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: 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}. Prove that Intersection Inference is NP-complete.