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, I am not sure it shows that the problem is NP-complete. The reason I am not sure is that, 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 Turing reduction.

Question: does my reduction show that Balanced Partition is NP-complete? If not, how can I fix it?

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?