1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

I will prove it is NP-hard leaving the proof that it is in NP to you.

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.