<p>The following problem is a decision problem of <em>multiway number partitioning</em> (<a href="https://en.wikipedia.org/wiki/Multiway_number_partitioning#:%7E:text=In%20computer%20science%2C%20multiway%20number,the%20Identical%2Dmachines%20scheduling%20problem." rel="nofollow noreferrer">wikipedia</a>) (Note that <span class="math-container">$k$</span> is also a part of an input in the following problem, while <span class="math-container">$k$</span> is a fixed number in wikipedia definition).</p>
<blockquote>
<p>Given <span class="math-container">$k, n \in \mathbb{N}$</span> and <span class="math-container">$n$</span> numbers <span class="math-container">$a_1, \ldots, a_n \in \mathbb{Z}$</span>, decide if there exists a partition of the numbers into <span class="math-container">$k$</span> parts so that the sum of numbers in each part equals <span class="math-container">$\frac{\sum a_i}{k}$</span>.</p>
</blockquote>
<p>As this problem includes the <a href="https://en.wikipedia.org/wiki/Partition_problem" rel="nofollow noreferrer">partition problem</a> as its special case (i.e. <span class="math-container">$k=2$</span>), multiway number partitioning is NP-hard.</p>
<p>I would like to know whether the hardness still holds for the following special case of multiway number partitioning (The only difference is that we assume each number is <span class="math-container">$0$</span> or <span class="math-container">$1$</span>).</p>
<blockquote>
<p>Given <span class="math-container">$k, n \in \mathbb{N}$</span> and <span class="math-container">$n$</span> numbers <span class="math-container">$a_1, \ldots, a_n \in \{0,1\}$</span>, decide if there exists a partition of the numbers into <span class="math-container">$k$</span> parts so that the sum of numbers in each part equals <span class="math-container">$\frac{\sum a_i}{k}$</span>.</p>
</blockquote>
<p>In this special case, when <span class="math-container">$k$</span> or <span class="math-container">$n-k$</span> is a fixed constant, it is easy to see that the problem is polynomial-time solvable.
This is because if <span class="math-container">$k$</span> is a constant, you can use dynamic programming and if <span class="math-container">$n-k$</span> is a constant, the number of possible partitions is at most the polynomial of <span class="math-container">$n$</span>, hence you can check the condition directly.</p>
<p>As there seems to be no efficient algorithm for middle size <span class="math-container">$k$</span>, I conjecture that multiway number partitioning for this special case is still NP-hard.</p>
<p>I would like to know if anybody knows about this.</p>

CC BY-SA 4.0
2022-01-13T17:02:05.260Z
Since all input numbers are $0$ or $1$, such a partition exists if and only if $(\sum a_i)/k$ is an integer. This is trivial to check in polynomial time.
Gamow
CC BY-SA 4.0
2022-01-14T00:10:58.820Z
Nice first question! Welcome to our community!
user1271772
CC BY-SA 4.0
2022-01-14T04:21:00.417Z
To extend @Gamow's observation, the straightforward dynamic program for a problem with element universe $U = \{0,1,...,u\}$ has running time $O(nku^{k-1})$. When $u=1$, the only truly expensive part of the algorithm drops out.
Yonatan N
CC BY-SA 4.0
2022-01-14T06:59:44.280Z
Thank you so much for the solultion. I should have come with that.
Ryoshun Oba
<np-hardness><time-complexity><partition-problem>
Is the following special case of multiway number partitioning NP-hard?
Ryoshun Oba
# Is the following special case of multiway number partitioning NP-hard?

(Asked by: username_0 on 2022-01-13)

The following problem is a decision problem of *multiway number partitioning* ([wikipedia](https://en.wikipedia.org/wiki/Multiway_number_partitioning#:%7E:text=In%20computer%20science%2C%20multiway%20number,the%20Identical%2Dmachines%20scheduling%20problem.)) (Note that $k$ is also a part of an input in the following problem, while $k$ is a fixed number in wikipedia definition).

> Given $k, n \in \mathbb{N}$ and $n$ numbers $a\_1, \ldots, a\_n \in \mathbb{Z}$, decide if there exists a partition of the numbers into $k$ parts so that the sum of numbers in each part equals $\frac{\sum a\_i}{k}$.

As this problem includes the [partition problem](https://en.wikipedia.org/wiki/Partition_problem) as its special case (i.e. $k=2$), multiway number partitioning is NP-hard.

I would like to know whether the hardness still holds for the following special case of multiway number partitioning (The only difference is that we assume each number is $0$ or $1$).

> Given $k, n \in \mathbb{N}$ and $n$ numbers $a\_1, \ldots, a\_n \in \{0,1\}$, decide if there exists a partition of the numbers into $k$ parts so that the sum of numbers in each part equals $\frac{\sum a\_i}{k}$.

In this special case, when $k$ or $n-k$ is a fixed constant, it is easy to see that the problem is polynomial-time solvable.
This is because if $k$ is a constant, you can use dynamic programming and if $n-k$ is a constant, the number of possible partitions is at most the polynomial of $n$, hence you can check the condition directly.

As there seems to be no efficient algorithm for middle size $k$, I conjecture that multiway number partitioning for this special case is still NP-hard.

I would like to know if anybody knows about this.

**Tags:** np-hardness, time-complexity, partition-problem
> **Comments:**
> **username_1**: Since all input numbers are $0$ or $1$, such a partition exists if and only if $(\sum a_i)/k$ is an integer. This is trivial to check in polynomial time.  
> **username_2**: Nice first question! Welcome to our community!  
> **username_3**: To extend @Gamow's observation, the straightforward dynamic program for a problem with element universe $U = \{0,1,...,u\}$ has running time $O(nku^{k-1})$. When $u=1$, the only truly expensive part of the algorithm drops out.  
> **username_0**: Thank you so much for the solultion. I should have come with that.  

---

## 0 answers

