Given an integer $k$ and $n$ sets $A_1,\ldots,A_n$, denote $U=A_1\cup A_2\cup\cdots\cup A_n$, $A_i^0=A_i$ and $A_i^1=U\backslash A_i$. The problem asks whether there exists $(b_1,\ldots, b_n)\in\{0,1\}^n$ such that


Is this problem NP-complete?

  • $\begingroup$ the space is $2^n$, right? $\endgroup$
    – kelalaka
    Commented Oct 7, 2018 at 18:29
  • $\begingroup$ I am not able to recall, but can you tell us whether the problem without the complement of each set is NP-complete? $\endgroup$
    – John L.
    Commented Oct 7, 2018 at 19:36
  • $\begingroup$ @kelalaka Yes, of course. $\endgroup$
    – xskxzr
    Commented Oct 8, 2018 at 2:27
  • $\begingroup$ @Apass.Jack Yes, it is NP-complete. $\endgroup$
    – xskxzr
    Commented Oct 8, 2018 at 2:30

1 Answer 1


This problem can be solved in polynomial time.

If $k=|U|$, this problem is exactly another wording for SAT where each clause contains all variables. More precisely, for each element $j\in U$, let $l_{ij}=b_i$ if $j\notin A_i$ while $l_{ij}=\neg b_i$ otherwise. The problem is exactly to satisfy the clauses $l_{1j}\vee l_{2j}\vee\cdots \vee l_{nj}$ for all $j$. If all possible clauses are involved in, the answer is certainly NO. Otherwise, without loss of generality, say one missing clause is $b_1\vee\cdots\vee b_n$, we can set $b_1=\cdots=b_n=0$ to satisfy all other clauses, thus the answer is YES.

If $k<|U|$, then at least one element should not be included in the union. We can test for each element: if this element is not included in the union, we can determine for each set whether it or its complement should be chosen, then we can see whether their union exactly has size $k$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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