# Decide whether this Problem NPC or P?

Input: A finite set A, subsets S1, . . . , Sn ⊆ A, and a number k ∈ N. Question: Does there exist a set R ⊆ A with |R| = k such that |R ∩ Si| = |Si| for all 1 ≤ i ≤ n? I read somewhere (without mentioning why) that it's an NP-complete problem, but I think it can be solved simply by taking the union of all subsets and comparing it to k. If it isn't equal to k, then we can't form a subset R ⊆ A with |R| = k such that |R ∩ Si| = |Si| for all 1 ≤ i ≤ n. is it an NPC problem or P problem ?

• Please edit your post to use Mathjax and formatting so it isn't all one big paragraph. See here for a short introduction.
– D.W.
Feb 22 at 20:38

Right, it is in $$\text{PTIME}$$. The condition $$|R\cap S_i| = |S_i|$$ is equivalent to $$S_i\subseteq R$$. So the problem is to find a subset $$R$$ whose size is $$k$$ and contains all sets in $$\{S_i\}_{i\in [n]}$$. In other words, $$\bigcup\limits_{i\in [n]} S_i \subseteq R$$. So you can simply find the smallest such set $$\bigcup\limits_{i\in [n]} S_i$$ and then compare $$|\bigcup\limits_{i\in [n]} S_i|$$ to $$k$$. If $$|\bigcup\limits_{i\in [n]} S_i| > k$$ or $$k > |A|$$, then there is no such set $$R$$. Otherwise, there is such a set.
As a conclusion, the problem is not known to be $$\text{NP-complete}$$, since we do not know yet whether $$\text{PTIME} = \text{NP}$$.