# NPC problem with sets

Let us have a finite set $S$ and a finite set of its subsets $S_1, S_2 \dots S_k$. For any $S_i$ we have two numbers: $l_i$ and $h_i$. We need to figure out if there is such a subset $T$ of $S$, that for any $i$ we have $l_i \leq |T \cap S_i| \leq h_i$.

Prove that this problem is in NP & NP-complete by reducing 3SAT to it.

Let $\phi = c_1\land c_2\dots\land c_m$ be a 3SAT formula. Define $$S = \{l \mid l \text { is a literal of } \phi \}$$ $$S_i = \{l \mid l \text { is a literal of } c_i\}$$
Since each clause has to have at least one literal with TRUE value we have the following constraints $$l_i=1 \leq |T \cap S_i|\leq 3 = h_i$$ Finally, we have to make sure that $T$ contains no variable $x$ (of $\phi$) and its negation at the same time $$S_{x} = \{x,\overline{x} \}$$ $$l_x=0\leq |T \cap S_x| \leq 1=h_x$$
So, if $\phi$ indeed has a solution then $T$ consists of those literals whose true-value is TRUE. Then it is trivial that all constraints satisfy since $T$ may not have a variable and its negation at the same time and each clause has at least one TRUE literal.
On the other hand, if we have a set $T$ satisfying the above-described constraints then $\phi$ can be constructed by ORing each literal in $S_i$ (by ORing with arbitrary variables if $|S_i| < 3$) and ANDing all clauses corresponding to $S_i$. This formula is satisfiable since may make each clause TRUE by making true each literal in $S_i$ and since not $x$ and $\overline{x}$ are in $T$.