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)?
NP completeness of linear $0-1$ assignment problem
linear programming;np complete;integer programming;subset sum;complexity
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$ zerosadd 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 -Band 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 sumSo 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  -BIn 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.