# Proof that Balanced Partition is NP-complete

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?

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.

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.

• OK, I see. I have now found this paper sciencedirect.com/science/article/pii/… which explains the difference between the completeness notions. So how can I prove that Balanced Partition is NP complete? Mar 2, 2022 at 17:38