*Bounty: 50*

*Bounty: 50*

In the `OrderedPartition`

problem, the input is two sequences of $n$ positive integers, $(a_i)*{iin [n]}$** and $(b_i)*{iin [n]}$.

The output is a partition of the indices $[n]$ into two disjoint subsets, $I$ and $J$, such that:

- $sum_{iin I} a_i = sum_{jin J} a_i$
- For all $iin I$ and for all $jin J$: $b_ileq b_j$.

In other words, we have to first order the indices on a line such that the $b_i$ are weakly increasing, and then cut the line such that the sum of the $a_i$ in both sides is the same.

If all $b_i$ are the same, then condition 2 is irrelevant and we have an instance of the NP-hard `Partition`

problem.

On the other hand, if all $b_i$ are different, then condition 2 imposes a single ordering on the indices, so there are only $n-1$ options to check, and the problem becomes polynomial. What happens in between these cases?

To formalize the question, define by `OrderedPartition[n,d]`

, for $1leq dleq n$,

the problem restricted to instances of size $n$, in which the largest subset of identical $b_i$-s is of size $d$. So the easy case, when all $b_i$-s are different, is `OrderedPartition[n,1]`

, and the hard case, when all $b_i$-s are identical, is `OrderedPartition[n,n]`

.

More generally, For any $n$ and $d$, in any `OrderedPartition[n,d]`

instance, the number of possible partitions respecting condition 2 is $O(n 2^d)$. Hence, if $din O(log{n})$, then `OrderedPartition[n,d]`

is still polynomial in $n$.

On the other hand, for any $n$ and $d$, we can reduce from a `Partition`

problem with $d$ integers to `OrderedPartition[n,d]`

. Let $p_1,ldots,p_d$ be an instance of `Partition`

. Define the instance `OrderedPartition[n,d]`

by:

- For each $iin {1,ldots,d}$, let $a_i := 2ncdot p_i$ and $b_i := 1$.
- For each $iin {d+1,ldots,n}$, let $a_i := 1$ and $b_i := i$

_{[if $n-d$ is odd, make $a_n:=2$ such that the sum will be even]}.

Hence, if $dinOmega(n^{1/k})$, for any integer $kgeq 1$, then `OrderedPartition[n,d]`

is NP-hard.

QUESTION: What happens in the intermediate cases, in which $d$ is super-logarithmic but sub-polynomial in $n$?