Return to Answer

Regarding 1. Consider a CNF-SAT formula $\phi$ with $n$ variables $x_1, \dots, x_n$ and $m$ clauses $C_1, \dots, C_m$. For $i=1,\dots,n$ define $s_{i,0} = \{ C_j \mid \overline{x}_i \in C_j\}$ and $s_{i,1} = \{ C_j \mid x_i \in C_j\}$.

The formula $\phi$ is satisfiable if and only if it is possible to select one $s^*_i \in \{s_{i,0}, s_{i,1}\}$ for each $i$ such that $\cup_{i=1}^n s^*_i = \{C_1, \dots, C_m\}$, i.e., $\left| \cup_{i=1}^n s^*_i \right|=m$. This shows that your variant of the problem is $\mathsf{NP}$-hard.

Regarding 2. The problem is equivalent to satisfying the maximum number of clauses in the CNF-SAT formula $\phi$ constructed as follows: create a variable $x_i$ for each pair $p_i = \{s_{i,0}, s_{i,1}\}$ and a clause $C_j$ for each element $a_j \in A$, where $C_j = \bigg( \bigvee\limits_{i : a_j \in s_{i,0}} \overline{x}_i \bigg) \vee \bigg( \bigvee\limits_{i : a_j \in s_{i,1}} x_i \bigg)$.

Since each $C_j$ contains all variables, $C_j$ is false only in $1$ out of the $2^n$ possible truth assignments. Therefore if the number of distinct clauses is less than $2^n$ we can always satisfy all clauses. Otherwise there is no way to satisfy all clauses. However we can pick one clause $C$ to "ignore" and satisfy all clauses $C_j \neq C$ (notice that there might be multiple clauses $C_j$ that equal $C$). We pick the clause $C$ that minimizes $|\{j : C_j = C\}|$. All of the above can be done in polynomial-time and shows that this version of your problem is not $\mathsf{NP}$-hard, unless $\mathsf{P}=\mathsf{NP}$.

Regarding 1. Consider a CNF-SAT formula $\phi$ with $n$ variables $x_1, \dots, x_n$ and $m$ clauses $C_1, \dots, C_m$. For $i=1,\dots,n$ define $s_{i,0} = \{ C_j \mid \overline{x}_i \in C_j\}$ and $s_{i,1} = \{ C_j \mid x_i \in C_j\}$.

The formula $\phi$ is satisfiable if and only if it is possible to select one $s^*_i \in \{s_{i,0}, s_{i,1}\}$ for each $i$ such that $\cup_{i=1}^n s^*_i = \{C_1, \dots, C_m\}$, i.e., $\left| \cup_{i=1}^n s^*_i \right|=m$. This shows that your variant of the problem is $\mathsf{NP}$-hard.

Regarding 2. The problem is equivalent to satisfying the maximum number of clauses in the CNF-SAT formula $\phi$ constructed as follows: create a variable $x_i$ for each pair $p_i = \{s_{i,0}, s_{i,1}\}$ and a clause $C_j$ for each element $a_j \in A$, where $C_j = \bigg( \bigvee\limits_{i : a_j \in s_{i,0}} \overline{x}_i \bigg) \vee \bigg( \bigvee\limits_{i : a_j \in s_{i,1}} x_i \bigg)$. Let $m = |A|$ be the number of clauses of $\phi$.

We say that two clauses are equivalent if they contain exactly the same literals and we look at the equivalence classes $\mathcal{C}_1, \mathcal{C}_2, \dots, \mathcal{C}_{\ell}$ of the set of clauses w.r.t. the relation "being equivalent".

Since each clause $C_j$ contains all variables, $C_j$ is false only in $1$ out of the $2^n$ possible truth assignments, and so are all clauses that are equivalent to $C_j$. This means that, if $\ell < 2^n$, there is always a truth assignment that satisfies all clauses.

We now consider the complementary case, namely $\ell \ge 2^n$. In this case it is impossible to satisfy all clauses simultaneously, i.e., in any truth assignment there is at least one clause equivalence class $\mathcal{C}$ such that all clauses in $\mathcal{C}$ are false.

Among all these classes we pick a class $\mathcal{C}^*$ that minimizes $|\mathcal{C}^*|$. From the above discussion we know that the formula $\phi^*$ obtained from $\phi$ by deleting the clauses in $\mathcal{C}^*$ is satisfiable and, by our choice of $\mathcal{C}^*$, we know that $m - |\mathcal{C}^*|$ is exactly the maximum number of satisfiable clauses of $\phi$.

All of the above can be done in polynomial-time and shows that this version of your problem is not $\mathsf{NP}$-hard, unless $\mathsf{P}=\mathsf{NP}$.

Regarding 1. Consider a CNF-SAT formula $\phi$ with $n$ variables $x_1, \dots, x_n$ and $m$ clauses $C_1, \dots, C_m$. For $i=1,\dots,n$ define $s_{i,0} = \{ C_j \mid \overline{x}_i \in C_j\}$ and $s_{i,1} = \{ C_j \mid x_i \in C_j\}$.

The formula $\phi$ is satisfiable if and only if it is possible to select one $s^*_i \in \{s_{i,0}, s_{i,1}\}$ for each $i$ such that $\cup_{i=1}^n s^*_i = \{C_1, \dots, C_m\}$, i.e., $\left| \cup_{i=1}^n s^*_i \right|=m$. This shows that your variant of the problem is $\mathsf{NP}$-hard.

Regarding 1. Consider a CNF-SAT formula $\phi$ with $n$ variables $x_1, \dots, x_n$ and $m$ clauses $C_1, \dots, C_m$. For $i=1,\dots,n$ define $s_{i,0} = \{ C_j \mid \overline{x}_i \in C_j\}$ and $s_{i,1} = \{ C_j \mid x_i \in C_j\}$.

The formula $\phi$ is satisfiable if and only if it is possible to select one $s^*_i \in \{s_{i,0}, s_{i,1}\}$ for each $i$ such that $\cup_{i=1}^n s^*_i = \{C_1, \dots, C_m\}$, i.e., $\left| \cup_{i=1}^n s^*_i \right|=m$. This shows that your variant of the problem is $\mathsf{NP}$-hard.

Regarding 2. The problem is equivalent to satisfying the maximum number of clauses in the CNF-SAT formula $\phi$ constructed as follows: create a variable $x_i$ for each pair $p_i = \{s_{i,0}, s_{i,1}\}$ and a clause $C_j$ for each element $a_j \in A$, where $C_j = \bigg( \bigvee\limits_{i : a_j \in s_{i,0}} \overline{x}_i \bigg) \vee \bigg( \bigvee\limits_{i : a_j \in s_{i,1}} x_i \bigg)$.

Since each $C_j$ contains all variables, $C_j$ is false only in $1$ out of the $2^n$ possible truth assignments. Therefore if the number of distinct clauses is less than $2^n$ we can always satisfy all clauses. Otherwise there is no way to satisfy all clauses. However we can pick one clause $C$ to "ignore" and satisfy all clauses $C_j \neq C$ (notice that there might be multiple clauses $C_j$ that equal $C$). We pick the clause $C$ that minimizes $|\{j : C_j = C\}|$. All of the above can be done in polynomial-time and shows that this version of your problem is not $\mathsf{NP}$-hard, unless $\mathsf{P}=\mathsf{NP}$.

Consider a CNF-SAT formula $\phi$ with $n$ variables $x_1, \dots, x_n$ and $m$ clauses $C_1, \dots, C_m$. For $i=1,\dots,n$ define $s_{i,0} = \{ C_j \mid \overline{x}_i \in C_j\}$ and $s_{i,1} = \{ C_j \mid x_i \in C_j\}$.

The formula $\phi$ is satisfiable if and only if it is possible to select one $s^*_i \in \{s_{i,0}, s_{i,1}\}$ for each $i$ such that $\cup_{i=1}^n s^*_i = \{C_1, \dots, C_m\}$, i.e., $\left| \cup_{i=1}^n s^*_i \right|=m$. This shows that your variant of the problem is NP-hard.

Regarding 1. Consider a CNF-SAT formula $\phi$ with $n$ variables $x_1, \dots, x_n$ and $m$ clauses $C_1, \dots, C_m$. For $i=1,\dots,n$ define $s_{i,0} = \{ C_j \mid \overline{x}_i \in C_j\}$ and $s_{i,1} = \{ C_j \mid x_i \in C_j\}$.

The formula $\phi$ is satisfiable if and only if it is possible to select one $s^*_i \in \{s_{i,0}, s_{i,1}\}$ for each $i$ such that $\cup_{i=1}^n s^*_i = \{C_1, \dots, C_m\}$, i.e., $\left| \cup_{i=1}^n s^*_i \right|=m$. This shows that your variant of the problem is $\mathsf{NP}$-hard.