0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Lev Reyzin Dec 13 '15 at 11:08
5
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Turbo Dec 12 '15 at 1:59
  • $\begingroup$ @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$ $\endgroup$ – Marzio De Biasi Dec 12 '15 at 2:03
  • $\begingroup$ I think I am not explaining well. $\endgroup$ – Turbo Dec 12 '15 at 2:11
  • 1
    $\begingroup$ @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). $\endgroup$ – Marzio De Biasi Dec 13 '15 at 2:50
  • 1
    $\begingroup$ Thank you it is just that I have not been formally introduced to these reductions. $\endgroup$ – Turbo Dec 13 '15 at 2:51
4
$\begingroup$

It seems that we can reduce Subset Sum 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.

$\endgroup$
  • 1
    $\begingroup$ How about Problem (1)? $\endgroup$ – Turbo Dec 10 '15 at 5:22
  • $\begingroup$ @Turbo I'm not sure. I will check back tomorrow though. :) $\endgroup$ – Michael Wehar Dec 10 '15 at 5:23
  • 1
    $\begingroup$ I had an idea to show (1a) and (1b) are $\mathsf{NP}$-complete and I have added my idea to my post. $\endgroup$ – Turbo Dec 10 '15 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.