Proof that Balanced Partition is NP-complete

Question

In the Balanced Partition problem, there are $2m$ nonnegative integers with sum $2s$. The goal is to decide whether they can be partitioned into two subsets of $m$ integers and sum $s$.

The problem is obviously in NP. I am trying to prove that it is NP-complete.

So far, I have found the following reduction from the standard Partition problem (which is the same problem but without the restriction on the number of integers). Given an instance $I$ of Partition with some $n$ integers, do for $k$ in $0,1,\ldots,n-1$:

• Add $k$ zeros to $I$ ;

• If $n+k$ is even, then try to find a balanced partition.

  • If a balanced partition is found, remove the zeros and return it.

If no partition is found for any $k$, return "No partition".

The algorithm is correct since, if a solution to the original instance $I$ exists, then we can add some $k$ zeros to one of the parts to get a balanced partition, so for this $k$, a balanced partition will be found.

This shows that Balanced Partition cannot be solved in polynomial-time unless P=NP. However, it does not show that the problem is NP-complete; according to this Wikipedia page, "a problem is NP-complete if it belongs to NP and all problems in NP have polynomial-time many-one reductions to it", while the reduction I just described is not a many-one reduction - it is a Cook reduction.

EDIT: this paper shows that completeness under Cook reduction is (under some assumptions) distinct than completeness under many-one (Karp-Levin) reductions (see also this cstheory.SE question).

Question: How can I prove that Balanced-Partition is NP-complete under a many-one reduction?

Answer 1

Instead of adding $k$ zeros for $k$ in $0,1,\ldots,n-1$, just adding $n$ zeros is enough. It is somewhat funny the reduction in the question is just one-off the right reduction.

---

Here is the detail. It is quite easy.

Let us reduce the partition problem, which is the task of deciding whether a given multiset of positive integers can be partitioned into two subsets with equal sum, to this "balanced partition problem".

Suppose $I=\text{multset}\{a_1, a_2, \cdots, a_n\}$, $a_i>0$ is (the input of) an instance of the partition problem.

Let $I'=\text{multset}\{a_1, a_2, \cdots, a_n, a_{n+1}=0, a_{n+2}=0, \cdots, a_{2n}=0\}$, i.e., $I$ with $n$ zeros added. $I'$ is an instance of the balanced partition problem.

• Suppose $I$ is a yes instance, i.e., there exists $I\subseteq\{1,2,\cdots, n\}$ such that $$\sum_{i\in I}a_i=\sum_{1\le i\le n,\,i\notin I}a_i.$$ Then $$\sum_{i\in J}a_i=\sum_{1\le i\le 2n,\,i\notin J}a_i,$$ where $J=I\cup\{i\mid n+1\le i\le 2n-|I|\}$. Since $|J|=2n/2$, we know $I'$ is a yes instance.
• Suppose $I'$ is a yes instance, i.e., there exists $J\subseteq\{1,2,\cdots, 2n\}$ such that $|J|=n$ and $$\sum_{i\in J}a_i=\sum_{1\le i\le 2n,\,i\notin J}a_i.$$ Removing all items that are $0$ from both sides, we obtain an equality that says $I$ is a yes instance.

The mapping from $I$ to $I'$ is a polynomial-time many-one reduction (a.k.a Karp reduction) from the partition problem to the balanced partition problem. (In fact, it is one-to-one reduction; however, "many-one" is good enough.) Since the former is $\mathsf{NP}$-complete and the latter is in $\mathsf{P}$, the latter is $\mathsf{NP}$-complete as well.

Answer 2

It sounds like you may already know the answer to your first question - the definition of NP-completeness requires you to find a many-one reduction, so no, you have not proven it to be NP-complete, but you have proven that if P!=NP then there is no polynomial-time algorithm for it. See also https://en.wikipedia.org/wiki/NP-completeness#Completeness_under_different_types_of_reduction.