<p>If I understood it well, (1) is also NP-complete, a possible reduction is from SUBSET SUM:</p>

<p>Given a set of $m$ positive integers $A = \{a_1, ..., a_m\}$, and a positive integer $B$, is there a subset of $A' \subseteq A$ a such that $\sum_{a_i \in A'} a_i$</p>

<p>You simply pick $n = (m+1)$ and build your set in this way:</p>

<ul>
<li>add $ a_1, a_2, , ..., a_m$</li>
<li>add $m$ zeros</li>
<li>add the only negative number $-B$</li>
<li>"fill" the other remaining $n^2 - 2m - 1$ elements with $C = \sum_{a_i} + B +1$</li>
</ul>

<p>($\Rightarrow$) If the original subset sum has a solution $A'$ then it is sufficient to use this partition $\Pi_1$</p>

<pre><code>a1  C  C  ... C  0  C
 0 a2  C  ... C  C  C
        ....
 C  C     ... 0 am  C
 C  C     ... C  C -B
</code></pre>

<p>and for each "row" pick $a_i$ if $a_i \in A'$, $0$ otherwise (and pick the final $-B$)</p>

<p>($\Leftarrow$) If there is a partition $\Pi_1$ with a vanishing 0/1 assignment then note that:</p>

<p>(i)  none of the $C$s can be picked (they are too large);<br>
(ii) at least one row must contain all elements different from $0$ (because there are $m+1$ rows and only $m$ zeros); so at least one nonzero element must be picked;<br>
(iii) in every case the $-B$ element must be picked to vanish the sum<br></p>

<p>So the elements $a_i$ picked, no matter how the elements are partitioned between the rows, sum exactly to $B$; i.e. they are a valid solution for the original SUBSET SUM problem.</p>

<p>OUCH! I just read Michael's answer about problem (2) and the reduction is almost the same ... so you can also accept his answer!</p>

<p><strong>EDIT</strong>: the reduction remains valid for the <strong>(1b)</strong> case:</p>

<p>The ($\Leftarrow$) direction it uses only the constraints on $\Pi_1$ which are the same of case 1a (exactly 1 "pick" from each row).</p>

<p>The ($\Rightarrow$) direction is also valid; to see it "visually", just build the main diagonal of $\Pi_1$ with the elements of $a_i \in A'$, the element $-B$, while the remaining elements of the diagonal are $0$s.</p>

<p>For example if $m = 5$ and the solution of the subset sum is $A' = \{ a_1, a_2, a_4 \}$, $\Pi_1$ is:</p>

<pre><code> a1  0  C   C  C   C
  C a2  0   C  C   C
  C  C  0  a3  C   C
  C  C  C  a4  0   C
  C  C  C   C  0  a5
  C  C  C   C  c  -B
</code></pre>

<p>In this way you can build $\Pi_2$ setting the element $j$ of row $i$-th equal to element $j$ of column $i$ in $\Pi_1$. The assignment clearly vanishes both $\Pi_1$ and $\Pi_2$ and the constraints are met.</p>

CC BY-SA 3.0
2015-12-12T01:59:40.573Z
SO is **(1b)** also NP complete? I can give you the bonus for what you have but if you can answer other problem also it will be great.
Turbo
CC BY-SA 3.0
2015-12-12T02:03:18.887Z
@Turbo: (1b) seems ill defined: if the total number of "picked numbers" is $n$, how can you pick "exactly" one number from $\Pi_1$ and "exactly" one number from $\Pi_2$
Marzio De Biasi
CC BY-SA 3.0
2015-12-12T02:11:25.963Z
I think I am not explaining well.
Turbo
CC BY-SA 3.0
2015-12-12T02:13:01.770Z
Consider disjoint sets $D_1,\dots,D_n$ of cardinality $n$ each. Make $E_1,\dots,E_n$ of cardinality $n$ each by picking one random member from each of $D_1,\dots,D_n$ in each of $E_i$ so that no member of $D_j$ is picked twice.
Turbo
CC BY-SA 3.0
2015-12-12T02:19:15.000Z
Ok, the $(\Leftarrow)$ part still holds because (1b) has the same conditions of (1a) for $\Pi_1$. Also the $(\Rightarrow)$ part seems to hold because I think that it's enough to arrange the pair of elements $(a_1,0)$, $(a_2,0)$ ... $(a_m,0)$, $(-B,C)$ (see the figure in the answer) along a diagonal.
Marzio De Biasi
CC BY-SA 3.0
2015-12-12T02:43:14.907Z
Can you make the **(1b)** proof more formal in your post?
Turbo
CC BY-SA 3.0
2015-12-12T10:00:46.427Z
Are you sure about $\implies$? It seems to be ok.
Turbo
CC BY-SA 3.0
2015-12-12T10:17:19.197Z
@Turbo: the assignment for $\Pi_1$ and $\Pi_2$ must be tha same or the two assignments can be different ? I.e. do you ask for an assignment that vanishes both $\Pi_1$ and $\Pi_2$, or two different assignments, one  must vanishe $\Pi_1$ and the other must vanish $\Pi_2$ ?
Marzio De Biasi
CC BY-SA 3.0
2015-12-12T10:23:24.657Z
One assignment agreeing on both partitions. is it still NP complete (diagonal trick seems working)?
Turbo
CC BY-SA 3.0
2015-12-12T10:36:40.847Z
I think yes (with a little caveat), see the modified answer.
Marzio De Biasi
CC BY-SA 3.0
2015-12-12T11:33:13.923Z
Very strange why didn't pure diagonal work?
Turbo
CC BY-SA 3.0
2015-12-12T11:43:15.973Z
@Turbo: IMO, it's pure diagonal work :-) ... but the unused $a_i$s, $0$s and the $C$s had to be placed somewhere
Marzio De Biasi
CC BY-SA 3.0
2015-12-12T11:51:25.103Z
looks staggered (is there a reason all diagnoal cannot be  variables?)
Turbo
CC BY-SA 3.0
2015-12-12T14:03:48.680Z
@Turbo: no, but I think it makes clearer that the 1-assignment is the same and that the "exactly 1" constraints are satisfied
Marzio De Biasi
CC BY-SA 3.0
2015-12-12T23:46:30.723Z
I am not clear on something. Is $\Pi_1$ and $\Pi_2$ simultaneously being satisfied. I want the assignment to simultaneously satisfy $\Pi_1$ and $\Pi_2$. What is the purpose of $a3,a5$ is second reduction?
Turbo
CC BY-SA 3.0
2015-12-13T02:50:38.797Z
@Turbo: $a_3, a_5$ are not part of the solution of the SUBSET SUM problem, so they are not "picked". The assignment induced by the SUBSET SUM instance vanishes both $\Pi_1$ and $\Pi_2$ (remember that we are proving the $\Rightarrow$ direction, i.e. if a valid solution of the SUBSET SUM instance exists, then the instance of your problem derived from it has also a solution).
Marzio De Biasi
CC BY-SA 3.0
2015-12-13T02:51:35.403Z
Thank you it is just that I have not been formally introduced to these reductions.
Turbo
CC BY-SA 3.0
2015-12-12T01:44:08.777Z
2015-12-12T10:36:18.217Z
2015-12-12T10:36:18.217Z
Marzio De Biasi
<p>It seems that we can reduce <a href="https://en.wikipedia.org/wiki/Subset_sum_problem" rel="nofollow">Subset Sum</a> to your problem (2).  Hence, your problem (2) is NP-complete.</p>

<p>Consider the following formulation of Subset Sum.</p>

<p><strong>Instance:</strong> A multi-set consisting of $n$ integers.</p>

<p><strong>Question:</strong> Does there exist a subset of size at least $1$ that sums to zero?</p>

<p>Now, we reduce Subset Sum to your problem (2).  Let a multi-set $X$ consisting of $n$ integers be given.  We construct a new multi-set $X'$ with $n^2$ integers by taking $X$ and adding integers to it.  </p>

<p>We throw $(n-1)$ zeros into $X$ and we throw $(n^2 - 2n + 1)$ very large numbers into $X$.  The very large numbers are large enough so that we can't choose any of them and still sum to zero.  However, we can either choose the zeros or not choose the zeros for a subset.</p>

<p>Now, we have that $X$ has a subset of size at least $1$ that sums to zero if and only if $X'$ has a subset of size exactly $n$ that sums to zero.</p>

<p>This $X'$ can be viewed as an instance for your problem 2.  Hence, we are done with the reduction.</p>

CC BY-SA 3.0
2015-12-10T05:22:55.107Z
How about Problem **(1)**?
Turbo
CC BY-SA 3.0
2015-12-10T05:23:57.403Z
@Turbo I'm not sure.  I will check back tomorrow though.  :)
Michael Wehar
CC BY-SA 3.0
2015-12-10T19:34:00.903Z
I had an idea to show **(1a)**  and **(1b)** are $\mathsf{NP}$-complete and I have added my idea to my post.
Turbo
CC BY-SA 3.0
2015-12-10T05:13:43.177Z
2015-12-10T05:19:11.990Z
2015-12-10T05:19:11.990Z
Michael Wehar
<p>Supposing we have a linear equation in $n^2$ variables with integer (negatives allowed) coefficients of at most $m$ bits each. </p>

<p>Partition $\Pi_1$ the variables into $n$ disjoint sets of $n$ variables each.</p>

<p>Make another partition $\Pi_2$ the following way. Pick $1$ variable in every disjoint set of variables in $\Pi_1$ form a new subset of variable of size $n$.  Pick $1$ variable in every disjoint set of variables in $\Pi_1$ not picked before to form a new subset of variable of size $n$. So we have another disjoint partition into $n$ disjoint sets of $n$ variables each.</p>

<p><strong>(1a)</strong> Is it $\mathsf{NP}$-complete to decide if there is a valid (valid here means vanishing) $0/1$ assignment with exactly $n$ of assignments to be $1$ with exactly $1$ assignment per disjoint set?</p>

<p><strong>(1b)</strong> Is it $\mathsf{NP}$-complete to decide if there is a valid (valid here means vanishing) $0/1$ assignment that satisfies exactly $n$ of assignments to be $1$ with exactly $1$ assignment per disjoint set $\Pi_1$ AND with exactly $1$ assignment per disjoint set $\Pi_2$?</p>

<p>Does subset sum reduce to both of these?</p>

<p>What is a good reduction from any $\mathsf{NP}$-complete problem?</p>

<p>It seems to me that the problem <strong>(1a)</strong> and <strong>(1b)</strong> qualify as some restricted version of $n$-sum problems. This seems to imply problem is $\mathsf{NP}$-complete. That is it is likely that some special case of $n$-sum reduces to these problems. Since $n$ is a function of number of variables $n^2$ are these problems $\mathsf{NP}$-complete?</p>

<hr>

<p>What if we add the promise that any satisfying assignment will have exactly $n$ $1$s?</p>

<hr>

<p><strong>(2)</strong> Is it $\mathsf{NP}$-complete to decide if there is a valid (valid here means vanishing) $0/1$ assignment with exactly $n$ of assignments to be $1$ (without regard to partition)? </p>

<p>has a trivial reduction as shown by Michael Wehar.</p>

<hr>

<p>A guess that we can think of <strong>(1a)</strong> as following:</p>

<p>Consider problem:</p>

<p><strong>(3)</strong> Given $n^2$ integers is there a way to partition the integers into disjoint subsets of size $n$ such that at least one of the subsets sum to $0$?</p>

<p>This problem sounds much similar to problem in definition $2$ in section $1.2$ here <a href="http://dreamboxx.com/mark/data/njc08.pdf" rel="nofollow">http://dreamboxx.com/mark/data/njc08.pdf</a>.</p>

<p>May be we can show <strong>(3)</strong> is $\mathsf{NP}$-complete and find a way to reduce <strong>(1a)</strong> to <strong>(3)</strong>?</p>

CC BY-SA 3.0
2015-12-13T11:08:08.340Z
Comments are not for extended discussion; this conversation has been [moved to chat](http://chat.stackexchange.com/rooms/32918/discussion-on-question-by-turbo-np-completeness-of-linear-0-1-assignment-probl).
Lev Reyzin
<linear-programming><np-complete><integer-programming><subset-sum><complexity>
NP completeness of linear $0-1$ assignment problem
Turbo
# NP completeness of linear $0-1$ assignment problem

(Asked by: username_0 on 2015-12-08)

Supposing we have a linear equation in $n^2$ variables with integer (negatives allowed) coefficients of at most $m$ bits each.

Partition $\Pi\_1$ the variables into $n$ disjoint sets of $n$ variables each.

Make another partition $\Pi\_2$ the following way. Pick $1$ variable in every disjoint set of variables in $\Pi\_1$ form a new subset of variable of size $n$. Pick $1$ variable in every disjoint set of variables in $\Pi\_1$ not picked before to form a new subset of variable of size $n$. So we have another disjoint partition into $n$ disjoint sets of $n$ variables each.

**(1a)** Is it $\mathsf{NP}$-complete to decide if there is a valid (valid here means vanishing) $0/1$ assignment with exactly $n$ of assignments to be $1$ with exactly $1$ assignment per disjoint set?

**(1b)** Is it $\mathsf{NP}$-complete to decide if there is a valid (valid here means vanishing) $0/1$ assignment that satisfies exactly $n$ of assignments to be $1$ with exactly $1$ assignment per disjoint set $\Pi\_1$ AND with exactly $1$ assignment per disjoint set $\Pi\_2$?

Does subset sum reduce to both of these?

What is a good reduction from any $\mathsf{NP}$-complete problem?

It seems to me that the problem **(1a)** and **(1b)** qualify as some restricted version of $n$-sum problems. This seems to imply problem is $\mathsf{NP}$-complete. That is it is likely that some special case of $n$-sum reduces to these problems. Since $n$ is a function of number of variables $n^2$ are these problems $\mathsf{NP}$-complete?

---

What if we add the promise that any satisfying assignment will have exactly $n$ $1$s?

---

**(2)** Is it $\mathsf{NP}$-complete to decide if there is a valid (valid here means vanishing) $0/1$ assignment with exactly $n$ of assignments to be $1$ (without regard to partition)?

has a trivial reduction as shown by username_3.

---

A guess that we can think of **(1a)** as following:

Consider problem:

**(3)** Given $n^2$ integers is there a way to partition the integers into disjoint subsets of size $n$ such that at least one of the subsets sum to $0$?

This problem sounds much similar to problem in definition $2$ in section $1.2$ here <http://dreamboxx.com/mark/data/njc08.pdf>.

May be we can show **(3)** is $\mathsf{NP}$-complete and find a way to reduce **(1a)** to **(3)**?

**Tags:** linear-programming, np-complete, integer-programming, subset-sum, complexity

> **Comments:**
> **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](http://chat.stackexchange.com/rooms/32918/discussion-on-question-by-turbo-np-completeness-of-linear-0-1-assignment-probl).  

---

## 2 answers

### Answer by username_2 on 2015-12-12. Score: 5 | Accepted answer

If I understood it well, (1) is also NP-complete, a possible reduction is from SUBSET SUM:
Given a set of $m$ positive integers $A = \{a_1, ..., a_m\}$, and a positive integer $B$, is there a subset of $A' \subseteq A$ a such that $\sum_{a_i \in A'} a_i$
You simply pick $n = (m+1)$ and build your set in this way:

add $ a_1, a_2, , ..., a_m$
add $m$ zeros
add the only negative number $-B$
"fill" the other remaining $n^2 - 2m - 1$ elements with $C = \sum_{a_i} + B +1$

($\Rightarrow$) If the original subset sum has a solution $A'$ then it is sufficient to use this partition $\Pi_1$
a1  C  C  ... C  0  C
 0 a2  C  ... C  C  C
        ....
 C  C     ... 0 am  C
 C  C     ... C  C -B

and for each "row" pick $a_i$ if $a_i \in A'$, $0$ otherwise (and pick the final $-B$)
($\Leftarrow$) If there is a partition $\Pi_1$ with a vanishing 0/1 assignment then note that:
(i)  none of the $C$s can be picked (they are too large);
(ii) at least one row must contain all elements different from $0$ (because there are $m+1$ rows and only $m$ zeros); so at least one nonzero element must be picked;
(iii) in every case the $-B$ element must be picked to vanish the sum
So the elements $a_i$ picked, no matter how the elements are partitioned between the rows, sum exactly to $B$; i.e. they are a valid solution for the original SUBSET SUM problem.
OUCH! I just read Michael's answer about problem (2) and the reduction is almost the same ... so you can also accept his answer!
EDIT: the reduction remains valid for the (1b) case:
The ($\Leftarrow$) direction it uses only the constraints on $\Pi_1$ which are the same of case 1a (exactly 1 "pick" from each row).
The ($\Rightarrow$) direction is also valid; to see it "visually", just build the main diagonal of $\Pi_1$ with the elements of $a_i \in A'$, the element $-B$, while the remaining elements of the diagonal are $0$s.
For example if $m = 5$ and the solution of the subset sum is $A' = \{ a_1, a_2, a_4 \}$, $\Pi_1$ is:
 a1  0  C   C  C   C
  C a2  0   C  C   C
  C  C  0  a3  C   C
  C  C  C  a4  0   C
  C  C  C   C  0  a5
  C  C  C   C  c  -B

In this way you can build $\Pi_2$ setting the element $j$ of row $i$-th equal to element $j$ of column $i$ in $\Pi_1$. The assignment clearly vanishes both $\Pi_1$ and $\Pi_2$ and the constraints are met.

> **Comments:**
> **username_0**: SO is **(1b)** also NP complete? I can give you the bonus for what you have but if you can answer other problem also it will be great.  
> **username_2**: @username_0: (1b) seems ill defined: if the total number of "picked numbers" is $n$, how can you pick "exactly" one number from $\Pi_1$ and "exactly" one number from $\Pi_2$  
> **username_0**: I think I am not explaining well.  
> **username_0**: Consider disjoint sets $D_1,\dots,D_n$ of cardinality $n$ each. Make $E_1,\dots,E_n$ of cardinality $n$ each by picking one random member from each of $D_1,\dots,D_n$ in each of $E_i$ so that no member of $D_j$ is picked twice.  
> **username_2**: Ok, the $(\Leftarrow)$ part still holds because (1b) has the same conditions of (1a) for $\Pi_1$. Also the $(\Rightarrow)$ part seems to hold because I think that it's enough to arrange the pair of elements $(a_1,0)$, $(a_2,0)$ ... $(a_m,0)$, $(-B,C)$ (see the figure in the answer) along a diagonal.  
> **username_0**: Can you make the **(1b)** proof more formal in your post?  
> **username_0**: Are you sure about $\implies$? It seems to be ok.  
> **username_2**: @username_0: the assignment for $\Pi_1$ and $\Pi_2$ must be tha same or the two assignments can be different ? I.e. do you ask for an assignment that vanishes both $\Pi_1$ and $\Pi_2$, or two different assignments, one  must vanishe $\Pi_1$ and the other must vanish $\Pi_2$ ?  
> **username_0**: One assignment agreeing on both partitions. is it still NP complete (diagonal trick seems working)?  
> **username_2**: I think yes (with a little caveat), see the modified answer.  
> **username_0**: Very strange why didn't pure diagonal work?  
> **username_2**: @username_0: IMO, it's pure diagonal work :-) ... but the unused $a_i$s, $0$s and the $C$s had to be placed somewhere  
> **username_0**: looks staggered (is there a reason all diagnoal cannot be  variables?)  
> **username_2**: @username_0: no, but I think it makes clearer that the 1-assignment is the same and that the "exactly 1" constraints are satisfied  
> **username_0**: I am not clear on something. Is $\Pi_1$ and $\Pi_2$ simultaneously being satisfied. I want the assignment to simultaneously satisfy $\Pi_1$ and $\Pi_2$. What is the purpose of $a3,a5$ is second reduction?  
> **username_2**: @username_0: $a_3, a_5$ are not part of the solution of the SUBSET SUM problem, so they are not "picked". The assignment induced by the SUBSET SUM instance vanishes both $\Pi_1$ and $\Pi_2$ (remember that we are proving the $\Rightarrow$ direction, i.e. if a valid solution of the SUBSET SUM instance exists, then the instance of your problem derived from it has also a solution).  
> **username_0**: Thank you it is just that I have not been formally introduced to these reductions.  

---

### Answer by username_3 on 2015-12-10. Score: 4

It seems that we can reduce [Subset Sum](https://en.wikipedia.org/wiki/Subset_sum_problem) to your problem (2). Hence, your problem (2) is NP-complete.

Consider the following formulation of Subset Sum.

**Instance:** A multi-set consisting of $n$ integers.

**Question:** Does there exist a subset of size at least $1$ that sums to zero?

Now, we reduce Subset Sum to your problem (2). Let a multi-set $X$ consisting of $n$ integers be given. We construct a new multi-set $X'$ with $n^2$ integers by taking $X$ and adding integers to it.

We throw $(n-1)$ zeros into $X$ and we throw $(n^2 - 2n + 1)$ very large numbers into $X$. The very large numbers are large enough so that we can't choose any of them and still sum to zero. However, we can either choose the zeros or not choose the zeros for a subset.

Now, we have that $X$ has a subset of size at least $1$ that sums to zero if and only if $X'$ has a subset of size exactly $n$ that sums to zero.

This $X'$ can be viewed as an instance for your problem 2. Hence, we are done with the reduction.

> **Comments:**
> **username_0**: How about Problem **(1)**?  
> **username_3**: @username_0 I'm not sure.  I will check back tomorrow though.  :)  
> **username_0**: I had an idea to show **(1a)**  and **(1b)** are $\mathsf{NP}$-complete and I have added my idea to my post.  

---

