<p>For any fixed $k$, isn't it in P, by dynamic programming?</p>

<p>For each $i\in\{0,\ldots,n\}$ and $t_1, t_2, ..., t_k$ such that each $t_i \in \{0,\ldots,m_i\}$, define $S(i, t_1, t_2, \ldots, t_k)$ to be true iff $(t_1, t_2, .., t_k)$ is $i$-realizable.  Then there are $O(n^{2k+1})$ such subproblems (assuming WLOG that $\max_i m_i\le n^2$), and you have a recurrence like</p>

<p>$ S(i, t_1, t_2, \ldots, t_k)$ </p>

<p>$~ = S(i-1, t_1 - i, t_2, \ldots, t_k) $</p>

<p>$~\vee~ S(i-1, t_1, t_2 - i, t_3, \ldots, t_k)$</p>

<p>$~\vee~ \cdots$</p>

<p>$~\vee~ S(i-1, t_1, t_2 , t_3, \ldots, t_{k-1}, t_k- i)?$</p>

CC BY-SA 3.0
2015-03-09T15:53:39.770Z
2015-03-09T16:00:01.040Z
2015-03-09T16:00:01.040Z
Neal Young
<p>This problem is known to be NP-complete in the strong sense.
See for instance<br>
<a href="https://cstheory.stackexchange.com/questions/709/cutting-sticks-puzzle/713#713">https://cstheory.stackexchange.com/questions/709/cutting-sticks-puzzle/713</a></p>

CC BY-SA 3.0
2015-03-09T07:47:22.510Z
@ Gamow: Thank you so much. But I actually had the proof that they suggested, by reduction from the partition problem instead of the 3-partition problem, quite a similar argument. I actually am looking for a proof that can be applied to any fixed value of $k$ (the number of sticks), for example, when $k=3$? Following the proof in that page, to achieve the NP-completeness for $k=3$, we have to set up, $a_1=1,\ldots,a_{3n}=N$, and $n=3$, which does not satisfy the conditions for the 3-partition problem, and indeed it is a very special instance of the problem!
user24175
CC BY-SA 3.0
2015-03-03T17:31:04.277Z
2015-03-03T17:31:04.277Z
2017-04-13T12:32:28.053Z
Gamow
<p>I saw this problem: </p>

<p>A non increasing sequence of positive integers $m_1,m_2,..., m_k$ is said to be <em>n-realizable</em> if the set $I_n=\{1,2,..., n\}$ can be partitioned into $k$ mutually disjoint subsets $S_1,S_2,...,S_k$ such that $\sum_{x\in S_i} x = m_i$ for each $1\leq i \leq k$. </p>

<p>in the paper "PARTITION OF A SET OF INTEGERS INTO SUBSETS WITH
PRESCRIBED SUMS", by Fu-Long Chen, Hung-Lin Fu, Yiju Wang and Jianqin Zhou </p>

<p><a href="http://journal.taiwanmathsoc.org.tw/index.php/TJM/article/view/1028" rel="nofollow">http://journal.taiwanmathsoc.org.tw/index.php/TJM/article/view/1028</a></p>

<p>They have solved the problem under certain constraints. But I can't find anything about its complexity in general. Does anyone know a reference about the complexity of this problem?
It reminds me of the bin-packing problem, or in some sense, it is similar to the subset sum problem. So, I guess it must be NP-complete in general?</p>

<p>More precisely, I like to prove the NP-completeness for the fixed value of $k$, for example, when $k = 3, 4, \ldots$?
In this case, it is very similar to bin-packing or knapsack problem, but as we want the equality it is different. Maybe there are variations of these problems that match my question?</p>

CC BY-SA 3.0
2015-02-28T19:33:20.103Z
I would be very surprised if this problem was NP-complete.
domotorp
CC BY-SA 3.0
2015-03-01T11:47:10.347Z
@user24175 Is it known to be polynomial time solvable if every $S_i$ has cardinality 2?
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-03-03T10:30:22.973Z
@mohammad If every $S_i$ has cardinality $2$, then we can reduce the problem to bipartite matching as follows. Consider $n$ vertices, labelled $1$ to $n$. There is an edge between vertex $i$ and vertex $j$ if there is a value $t$ such that $i + j = m_t$.
S. Pek
CC BY-SA 3.0
2015-03-03T12:13:47.223Z
@S.Pek That is incorrect. We need to find a restricted perfect matching with certain some ($\sum m_i$  ) If we want any perfect matching then the problem is polynomial time solvable. So, the problem probably is $NP$-complete even if every $S_i$ has cardinality 2.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-03-03T12:46:23.250Z
@mohammad It is not $\sum m_i$, but rather $\sum_{x \in S_i} x = m_i$.
S. Pek
CC BY-SA 3.0
2015-03-03T16:29:08.943Z
@S.Pek Any perfect matching does not guarantee that each $m_i$ appears the right number of times in the matching. For instance, a perfect matching with all edges having $m_1$ is not a valid solution for the problem.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-03-09T19:30:03.563Z
@user24175 The variant asking for a partition of $I_n$ with prescribed differences is NP-complete even if the cardinality of each $S_i$ is 2. I am working on a reduction from this problem to yours.
Mohammad Al-Turkistany
<cc.complexity-theory>
Partition of a set of integers into subsets with prescribed sums
user24175
# Partition of a set of integers into subsets with prescribed sums

(Asked by: username_0 on 2015-02-28)

I saw this problem:

A non increasing sequence of positive integers $m\_1,m\_2,..., m\_k$ is said to be *n-realizable* if the set $I\_n=\{1,2,..., n\}$ can be partitioned into $k$ mutually disjoint subsets $S\_1,S\_2,...,S\_k$ such that $\sum\_{x\in S\_i} x = m\_i$ for each $1\leq i \leq k$.

in the paper "PARTITION OF A SET OF INTEGERS INTO SUBSETS WITH
PRESCRIBED SUMS", by Fu-Long Chen, Hung-Lin Fu, Yiju Wang and Jianqin Zhou

<http://journal.taiwanmathsoc.org.tw/index.php/TJM/article/view/1028>

They have solved the problem under certain constraints. But I can't find anything about its complexity in general. Does anyone know a reference about the complexity of this problem?
It reminds me of the bin-packing problem, or in some sense, it is similar to the subset sum problem. So, I guess it must be NP-complete in general?

More precisely, I like to prove the NP-completeness for the fixed value of $k$, for example, when $k = 3, 4, \ldots$?
In this case, it is very similar to bin-packing or knapsack problem, but as we want the equality it is different. Maybe there are variations of these problems that match my question?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: I would be very surprised if this problem was NP-complete.  
> **username_2**: @username_0 Is it known to be polynomial time solvable if every $S_i$ has cardinality 2?  
> **username_3**: @mohammad If every $S_i$ has cardinality $2$, then we can reduce the problem to bipartite matching as follows. Consider $n$ vertices, labelled $1$ to $n$. There is an edge between vertex $i$ and vertex $j$ if there is a value $t$ such that $i + j = m_t$.  
> **username_2**: @S.Pek That is incorrect. We need to find a restricted perfect matching with certain some ($\sum m_i$  ) If we want any perfect matching then the problem is polynomial time solvable. So, the problem probably is $NP$-complete even if every $S_i$ has cardinality 2.  
> **username_3**: @mohammad It is not $\sum m_i$, but rather $\sum_{x \in S_i} x = m_i$.  
> **username_2**: @S.Pek Any perfect matching does not guarantee that each $m_i$ appears the right number of times in the matching. For instance, a perfect matching with all edges having $m_1$ is not a valid solution for the problem.  
> **username_2**: @username_0 The variant asking for a partition of $I_n$ with prescribed differences is NP-complete even if the cardinality of each $S_i$ is 2. I am working on a reduction from this problem to yours.  

---

## 2 answers

### Answer by username_4 on 2015-03-09. Score: 3

For any fixed $k$, isn't it in P, by dynamic programming?

For each $i\in\{0,\ldots,n\}$ and $t\_1, t\_2, ..., t\_k$ such that each $t\_i \in \{0,\ldots,m\_i\}$, define $S(i, t\_1, t\_2, \ldots, t\_k)$ to be true iff $(t\_1, t\_2, .., t\_k)$ is $i$-realizable. Then there are $O(n^{2k+1})$ such subproblems (assuming WLOG that $\max\_i m\_i\le n^2$), and you have a recurrence like

$ S(i, t\_1, t\_2, \ldots, t\_k)$

$~ = S(i-1, t\_1 - i, t\_2, \ldots, t\_k) $

$~\vee~ S(i-1, t\_1, t\_2 - i, t\_3, \ldots, t\_k)$

$~\vee~ \cdots$

$~\vee~ S(i-1, t\_1, t\_2 , t\_3, \ldots, t\_{k-1}, t\_k- i)?$


---

### Answer by username_5 on 2015-03-03. Score: 2

This problem is known to be NP-complete in the strong sense.
See for instance  
[https://cstheory.stackexchange.com/questions/709/cutting-sticks-puzzle/713](https://cstheory.stackexchange.com/questions/709/cutting-sticks-puzzle/713#713)

> **Comments:**
> **username_0**: @ username_5: Thank you so much. But I actually had the proof that they suggested, by reduction from the partition problem instead of the 3-partition problem, quite a similar argument. I actually am looking for a proof that can be applied to any fixed value of $k$ (the number of sticks), for example, when $k=3$? Following the proof in that page, to achieve the NP-completeness for $k=3$, we have to set up, $a_1=1,\ldots,a_{3n}=N$, and $n=3$, which does not satisfy the conditions for the 3-partition problem, and indeed it is a very special instance of the problem!  

---

