a question about complexity of Boolean problem

Question

I was thinking in solving the following problem for the general case :

**) Given a list of pairs $((n_i, A_i))_{i=1}^k$, where for each $i$ we have that $n_i $ is a non-negative integer, and $A_i$ is a set, does there exist a set $A$ such that $|A\cap A_i|=n_i$?

Example 1 : Given as an input the list : $(3, \{a,b,c\}), (4, \{a,b,c,d,e,f\}), (2, \{a,b,c,d\})$ the answer will be negative, because from the first set we are forced to take all the 3 elements $a$,$b$ and $c$ but from the last set we must take just 2 elements but it's already containing 3 elements that we forced to pick.

Example 2 : Given as an input the list : $(2, \{a,b,c\}), (3, \{a,b,c,d\}), (4, \{a,b,c,d,e,f\})$ the answer is positive, for instance we can pick $\{a,b,d,f\}$.

My question is : is the General case of this problem solvable in Exp,SubExp,Quasi-Poly,Poly time ? space ?

Answer 1

The problem is visibly in NP, as we can check in polynomial time whether a given set $A$ is a correct witness.

In fact, the problem is NP-complete, and one can show this by reduction from the NP-complete problem 1-in-3-SAT: given a 3-CNF in variables $x_1,\dots,x_n$ with clauses $C_1,\dots,C_m$, we reduce it to the list $$(1,\{x_1,\overline{x_1}\}),\dots,(1,\{x_n,\overline{x_n}\}),(1,C_1),\dots,(1,C_m).$$ (The clauses $C_i$ are here treated as subsets of the $2n$-element set of literals $\{x_1,\dots,x_n,\overline{x_1},\dots,\overline{x_n}\}$.)

The problem remains NP-complete when restricted to the case where all $n_i=1$, and all the sets $A_i$ have three elements. The reduction above almost achieves this, except that some of the sets have only two elements. This is easy to fix: for example, we may replace a two-element set $(1,\{a,b\})$ with the input $(1,\{a,b,u\}),(1,\{a,b,v\}),(1,\{u,v,w\})$ where $u,v,w$ are three new elements.