<p>Your problem is NP-complete.</p>

<p>I prove NP-hardness below by reduction from the clique problem (given a graph and a number, does the graph have a clique of that many vertices).</p>

<h2>reduction</h2>

<p>Suppose we are given a clique instance consisting of a graph $G = (V, E)$ with $m = |E|$ and $n = |V|$ and a number $k$. Then we will produce an instance of your problem consisting of a formula $\phi$ and a number $K$ as described below</p>

<p>First of all, we set $K = k + (n+1) \times {k \choose 2}$.</p>

<p>Next, lets describe the variables used in $\phi$. For each vertex $v \in V$, $\phi$ will include a variable $x_v$. For each edge $e \in E$, $\phi$ will include $n+1$ variables: $y_e^0, y_e^1, \ldots, y_e^n$.</p>

<p>Finally, lets describe the clauses included in $\phi$. Each clauses has the form $(a \vee \neg b)$, which is logically equivalent to $(b \to a)$, so I will write all clauses in implication form. For each edge $e \in E$, we include clauses $(y_e^n \to y_e^0)$, $(y_e^0 \to y_e^1)$, $(y_e^1 \to y_e^2)$, ..., and $(y_e^{n-1} \to y_e^n)$. The effect of these clauses is to enforce the equality of all the $y_e^i$s (for any fixed $e$) in any satisfying assignment. Next, for any edge $(u, v) \in E$, we also include clauses $(y_{(u,v)}^0 \to x_u)$ and $(y_{(u,v)}^0 \to x_v)$. The effect of these clauses is that in any satisfying assignment, if the variables $y_{(u,v)}^i$ associated with an edge are true then the variables $x_u$ and $x_v$ associated with the endpoints must also be true.</p>

<h2>clique $\to$ satisfying assignment</h2>

<p>Suppose that there is a clique $C$ of size $k$ in $G$. Then we can create a satisfying assignment for $\phi$ with exactly $K = k + (n+1) \times {k \choose 2}$ true variables.</p>

<p>In particular, for $v \in V$, set $x_v$ to true iff $v \in C$, and for $e \in E$, set $y_e^i$ to true iff both endpoints of $e$ are in $C$.</p>

<p>There are $n+1$ variables $y_e^i$ for each $e$, and there are exactly $k \choose 2$ edges in $G$ with both endpoints in $C$ (since $C$ is a clique). Thus there are $(n+1) \times {k \choose 2}$ variables of the form $y_e^i$ that are set to true under this assignment. Furthermore, $|C| = k$, so there are exactly $k$ variables of the form $x_v$ set to true under this assignment. As desired, this assignment has exactly $K = k + (n+1) \times {k \choose 2}$ true variables.</p>

<p>Notice that $y_e^i = y_e^j$ for every edge $e$ and pair of indices $i, j$. Thus, the clauses of the form $(y_e^i \to y_e^{(i+1)~\text{mod}~(n+1)})$ are satisfied under this variable assignment. </p>

<p>Next, consider any edge $(u, v)$. If $y_{(u, v)}^0$ is true, then both $u$ and $v$ are vertices in $C$, so therefore both $x_u$ and $x_v$ are also true. Thus, clauses $(y_{(u,v)}^0 \to x_u)$ and $(y_{(u,v)}^0 \to x_v)$ are also satisfied.</p>

<p>Since all clauses are satisfied, this is a satisfying assignment (which we already noted has exactly $K$ true variables).</p>

<h2>satisfying assignment $\to$ clique</h2>

<p>Next suppose we have a satisfying assignment of $\phi$ with exactly $K = k+ (n+1) \times {k \choose 2}$ true variables.</p>

<p>Any satisfying assignment has $y_e^0 = y_e^1 = \cdots = y_e^n$. Then let $y_e = y_e^0$. Define $n_y$ to be the number of true $y_e$s. Similarly, define $n_x$ to be the number of true $x_v$s. Notice that the number of true variables in the assignment is equal to $n_x + (n+1) \times n_y$. Furthermore, $0 \le n_x &lt; n+1$ since there are only $n$ different $x_v$s. Thus, we can conclude that $n_x = K~\text{mod}~(n+1) = k$ and $n_y = \lfloor \frac{K}{n+1} \rfloor = {k \choose 2}$.</p>

<p>Let $C = \{v \in V~|~x_v~\text{is true}\}$ and let $E' = \{e \in E~|~y_e~\text{is true}\}$. Note that $|C| = n_x$ and $|E'| = n_y$ by definition. Then $E'$ is a set of ${k \choose 2}$ edges, and $C$ is a set of $k$ edges. </p>

<p>Notice that if $(u,v) \in E'$, then $y_{(u,v)}$ is true, and therefore $y_{(u,v)}^0$ is true; as a result, since clauses $(y_{(u,v)}^0 \to x_u)$ and $(y_{(u,v)}^0 \to x_v)$ must be satisfied, we can conclude that $x_u$ and $x_v$ are also true, and therefore that $u,v \in C$. Thus, if $e \in E'$ and $v$ is an endpoint of $e$ then $v \in C$. </p>

<p>Thus the set of endpoints of edges in $E'$ is a subset of $C$. Then $E'$ is a set of ${k \choose 2}$ edges whose set of endpoints numbers at most $|C| = k$. A set of ${k \choose 2}$ edges has only $k$ endpoints in total only in the case that the $k$ endpoints are a clique. In other words, it must be the case that $C$ is a clique and the edges in $E'$ are the edges in the clique.</p>

<p>Thus we have identified a clique of size $k$ in $G$.</p>

CC BY-SA 3.0
2017-05-30T07:03:28.453Z
Much thanks. The reduction is complicated so it will take some time for me to process it.. :)
TheoryQuest1
CC BY-SA 3.0
2017-05-29T23:43:05.700Z
2017-05-29T23:43:05.700Z
Mikhail Rudoy
<p>Given a 2HornSAT problem, it’s possible in linear time to find the minimum solution to the problem, i.e., a solution that minimizes the number of variables set to 1.</p>

<p>Now let us consider the following restricted variant of that problem:</p>

<blockquote>
  <p><strong>Input:</strong>​ A positive integer $K$ and a 2SAT instance in which all clauses are mixed, i.e., have a positive literal and a negative literal.</p>
  
  <p><strong>Output:</strong> Is there a satisfying assignment such that exactly $K$ variables are set to 1?</p>
</blockquote>

<p>Is this problem NP-complete? I am struggling with its reduction but it seems this might be difficult.</p>

CC BY-SA 3.0
2017-05-31T16:06:25.087Z
Comments are not for extended discussion; this conversation has been [moved to chat](http://chat.stackexchange.com/rooms/59634/discussion-on-question-by-theoryquest1-totally-mixed-2sat-with-exact-cardinality).
Lev Reyzin
<cc.complexity-theory><np-hardness>
totally-mixed 2SAT with exact cardinality?
TheoryQuest1
# totally-mixed 2SAT with exact cardinality?

(Asked by: username_0 on 2017-05-24)

Given a 2HornSAT problem, it’s possible in linear time to find the minimum solution to the problem, i.e., a solution that minimizes the number of variables set to 1.

Now let us consider the following restricted variant of that problem:

> **Input:**​ A positive integer $K$ and a 2SAT instance in which all clauses are mixed, i.e., have a positive literal and a negative literal.
>
> **Output:** Is there a satisfying assignment such that exactly $K$ variables are set to 1?

Is this problem NP-complete? I am struggling with its reduction but it seems this might be difficult.

**Tags:** cc.complexity-theory, np-hardness

> **Comments:**
> **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](http://chat.stackexchange.com/rooms/59634/discussion-on-question-by-theoryquest1-totally-mixed-2sat-with-exact-cardinality).  

---

## 1 answers

### Answer by username_2 on 2017-05-29. Score: 7 | Accepted answer

Your problem is NP-complete.

I prove NP-hardness below by reduction from the clique problem (given a graph and a number, does the graph have a clique of that many vertices).

## reduction

Suppose we are given a clique instance consisting of a graph $G = (V, E)$ with $m = |E|$ and $n = |V|$ and a number $k$. Then we will produce an instance of your problem consisting of a formula $\phi$ and a number $K$ as described below

First of all, we set $K = k + (n+1) \times {k \choose 2}$.

Next, lets describe the variables used in $\phi$. For each vertex $v \in V$, $\phi$ will include a variable $x\_v$. For each edge $e \in E$, $\phi$ will include $n+1$ variables: $y\_e^0, y\_e^1, \ldots, y\_e^n$.

Finally, lets describe the clauses included in $\phi$. Each clauses has the form $(a \vee \neg b)$, which is logically equivalent to $(b \to a)$, so I will write all clauses in implication form. For each edge $e \in E$, we include clauses $(y\_e^n \to y\_e^0)$, $(y\_e^0 \to y\_e^1)$, $(y\_e^1 \to y\_e^2)$, ..., and $(y\_e^{n-1} \to y\_e^n)$. The effect of these clauses is to enforce the equality of all the $y\_e^i$s (for any fixed $e$) in any satisfying assignment. Next, for any edge $(u, v) \in E$, we also include clauses $(y\_{(u,v)}^0 \to x\_u)$ and $(y\_{(u,v)}^0 \to x\_v)$. The effect of these clauses is that in any satisfying assignment, if the variables $y\_{(u,v)}^i$ associated with an edge are true then the variables $x\_u$ and $x\_v$ associated with the endpoints must also be true.

## clique $\to$ satisfying assignment

Suppose that there is a clique $C$ of size $k$ in $G$. Then we can create a satisfying assignment for $\phi$ with exactly $K = k + (n+1) \times {k \choose 2}$ true variables.

In particular, for $v \in V$, set $x\_v$ to true iff $v \in C$, and for $e \in E$, set $y\_e^i$ to true iff both endpoints of $e$ are in $C$.

There are $n+1$ variables $y\_e^i$ for each $e$, and there are exactly $k \choose 2$ edges in $G$ with both endpoints in $C$ (since $C$ is a clique). Thus there are $(n+1) \times {k \choose 2}$ variables of the form $y\_e^i$ that are set to true under this assignment. Furthermore, $|C| = k$, so there are exactly $k$ variables of the form $x\_v$ set to true under this assignment. As desired, this assignment has exactly $K = k + (n+1) \times {k \choose 2}$ true variables.

Notice that $y\_e^i = y\_e^j$ for every edge $e$ and pair of indices $i, j$. Thus, the clauses of the form $(y\_e^i \to y\_e^{(i+1)~\text{mod}~(n+1)})$ are satisfied under this variable assignment.

Next, consider any edge $(u, v)$. If $y\_{(u, v)}^0$ is true, then both $u$ and $v$ are vertices in $C$, so therefore both $x\_u$ and $x\_v$ are also true. Thus, clauses $(y\_{(u,v)}^0 \to x\_u)$ and $(y\_{(u,v)}^0 \to x\_v)$ are also satisfied.

Since all clauses are satisfied, this is a satisfying assignment (which we already noted has exactly $K$ true variables).

## satisfying assignment $\to$ clique

Next suppose we have a satisfying assignment of $\phi$ with exactly $K = k+ (n+1) \times {k \choose 2}$ true variables.

Any satisfying assignment has $y\_e^0 = y\_e^1 = \cdots = y\_e^n$. Then let $y\_e = y\_e^0$. Define $n\_y$ to be the number of true $y\_e$s. Similarly, define $n\_x$ to be the number of true $x\_v$s. Notice that the number of true variables in the assignment is equal to $n\_x + (n+1) \times n\_y$. Furthermore, $0 \le n\_x < n+1$ since there are only $n$ different $x\_v$s. Thus, we can conclude that $n\_x = K~\text{mod}~(n+1) = k$ and $n\_y = \lfloor \frac{K}{n+1} \rfloor = {k \choose 2}$.

Let $C = \{v \in V~|~x\_v~\text{is true}\}$ and let $E' = \{e \in E~|~y\_e~\text{is true}\}$. Note that $|C| = n\_x$ and $|E'| = n\_y$ by definition. Then $E'$ is a set of ${k \choose 2}$ edges, and $C$ is a set of $k$ edges.

Notice that if $(u,v) \in E'$, then $y\_{(u,v)}$ is true, and therefore $y\_{(u,v)}^0$ is true; as a result, since clauses $(y\_{(u,v)}^0 \to x\_u)$ and $(y\_{(u,v)}^0 \to x\_v)$ must be satisfied, we can conclude that $x\_u$ and $x\_v$ are also true, and therefore that $u,v \in C$. Thus, if $e \in E'$ and $v$ is an endpoint of $e$ then $v \in C$.

Thus the set of endpoints of edges in $E'$ is a subset of $C$. Then $E'$ is a set of ${k \choose 2}$ edges whose set of endpoints numbers at most $|C| = k$. A set of ${k \choose 2}$ edges has only $k$ endpoints in total only in the case that the $k$ endpoints are a clique. In other words, it must be the case that $C$ is a clique and the edges in $E'$ are the edges in the clique.

Thus we have identified a clique of size $k$ in $G$.

> **Comments:**
> **username_0**: Much thanks. The reduction is complicated so it will take some time for me to process it.. :)  

---

