1
$\begingroup$

A: Given nonnegative integers x1,...,xn (written in binary), and an integer k, can the net expenses be balanced using k or fewer checks? (Suppose that A is in NP).

Purpose: to reveal that SUBSET SUM reduces to A so that A is NP-complete (since SUBSET SUM is NP-complete).

Let me construct A as follows:

  1. We can find the balanced net expense using SUBSET SUM.
  • The balanced net expense = (x1+x2+...+xn)/n
  1. There will be some algorithm to compute k.

What I wonder is that as we see the algorithm above A seems to be a harder problem than SUBSET SUM because A uses SUBSET SUM within its algorithm. Is this fact enough to support the idea that SUBSET SUM is reducible to A?

Thank you for your time.

$\endgroup$
2
$\begingroup$

You can consider the numbers $x_i$ as signed integers representing how much each person owes (if the number is positive) or how much each person needs to receive (if the number is negative). Then you have $\sum_{i=1}^n x_i = 0$ and the goal is to make all numbers $0$.

Notice that you can always settle debts with at most $n-1$ checks: pick an $i$ such that $x_i>0$ and move $x_i$ from $i$ to an arbitrary $j \neq i$. Delete $x_i$ (now $0$) from the instance. You are left with another instance of the same problem in which you need settle debts between $n-1$ people. Repeat recursively until you are left with only one person (in which cases no transactions are needed).

Suppose now that you can partition the set $\{x_1, \dots, x_n\}$ into two non-empty sets $S_1$ and $S_2$ such that $\sum_{x \in S_1} x =0$ (and hence $\sum_{x \in S_2} x = 0$). Then you can solve $S_1$ and $S_2$ separately using at most $|S_1|-1 + |S_2|-1 = n-2$ checks.

The converse is also true: if you can balance debts using at most $n-2$ checks, then you can partition $\{x_1, \dots, x_n\}$ into non-empty $S_1$ and $S_2$ with $\sum_{x \in S_1} x = \sum_{x \in S_2} x = 0$. To see this, build the graph $G=(V,E)$ in which $V=\{1, \dots, n\}$ and there is an undirected edge $(i,j)$ if $i$ and $j$ exchange at least one check. Since $|E| \le n-2 = |V|-2$, the graph $G$ has at least $2$ connected component. If $C$ is a connected component then the sum of the integers $x_i$ such that $i \in C$ must be $0$. Let $S_1 = \{x_i \mid i \in C\}$ and $S_2 = \{x_1, \dots, x_n\} \setminus S_1$.

This shows that you can reduce the variant of partition in which the sum of the integers is $0$ (and you need to find a non-trivial partition) to your problem. To see that this variant remains $\mathsf{NP}$-hard, consider an instance of partition $\{y_1, \dots, y_n\}$ in which each integer $y_i$ is positive, and add two additional integers $y'$ and $y''$ with $y'=y''= -\frac{1}{2}\sum_{i=1}^n y_i$. Clearly, any non-trivial partition $A,B$ of $\{y', y'', y_1, \dots, y_n\}$ must place $y'$ in $A$ and $y''$ in $B$, or vice-versa, showing that the sum of the elements in $A \cap \{ y_1, \dots, y_n\}$ is $\frac{1}{2}\sum_{i=1}^n y_i$ (and the same holds for $B$). Conversely, given any partition $A,B$ of $\{y_1, \dots, y_n\}$, the partition $A \cup \{y'\}$, $B \cup \{y''\}$ is a solution to our variant.

$\endgroup$
14
  • $\begingroup$ Suppose n people live in a house and wish to share their expenses equally. Their respective expenses (before settling) are x1, ..., xn. They agree to write checks to each other so as to make all their net expenses equal. $\endgroup$ – Matthew Apr 9 at 21:40
  • $\begingroup$ This is the given information for this problem, and I think x1,...,xn are non-negative integers I guess? So, we may not need to care about the case when the expenses are negative? $\endgroup$ – Matthew Apr 9 at 21:41
  • $\begingroup$ So, you suppose that x1,...,xn will be represented as signed integers, right? But, can the expenses be negative? Aren't they supposed to be like 0,3,3,2? The 1st person's expense is 0, the 2nd person's expense is 3, and so on. $\endgroup$ – Matthew Apr 9 at 21:48
  • $\begingroup$ Again, $x_i$ is positive if the $i$-th person paid $x_i$ less than the average expense. $x_i$ is negative if the $i$-th person paid $-x_i$ more than the average expense. $\endgroup$ – Steven Apr 9 at 21:52
  • 1
    $\begingroup$ Now I am slowly understanding your logic. Thanks for your help! $\endgroup$ – Matthew Apr 9 at 23:59

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.