NP completeness of linear $0-1$ assignment problem 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 Michael Wehar.



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)?
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.