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 ?



a question about complexity of Boolean problem
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](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Exactly-1_3-satisfiability): 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.


