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 Oct 7 '18 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. Oct 7 '18 at 19:36
  • $\begingroup$ @kelalaka Yes, of course. $\endgroup$ – xskxzr Oct 8 '18 at 2:27
  • $\begingroup$ @Apass.Jack Yes, it is NP-complete. $\endgroup$ – xskxzr Oct 8 '18 at 2:30

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

| cite | improve this answer | |

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.