A partition problem with order constraints In the OrderedPartition problem, the input is two sequences of $n$ positive integers, $(a_i)_{i\in [n]}$ and $(b_i)_{i\in [n]}$.
The output is a partition of the indices $[n]$ into two disjoint subsets, $I$ and $J$, such that:


$\sum_{i\in I} a_i = \sum_{j\in J} a_i$
For all $i\in I$ and for all $j\in J$: $b_i\leq 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 $1\leq d\leq 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 $d\in 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 an instance of OrderedPartition[n,d] by:


For each $i\in \{1,\ldots,d\}$, let $a_i := 2n\cdot p_i$ and $b_i := 1$.
For each $i\in \{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 $d\in\Omega(n^{1/k})$, for any integer $k\geq 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$?
Intuitively, the intermediate cases should be neither in P, nor NP-hard.  Perhaps it depends exactly on what we mean by "intermediate case".  Here is one interpretation for which we can prove something.

Note: The Exponential-Time Hypothesis, or ETH, is that it is not the case that, for every constant $\epsilon&gt;0$, SAT has an algorithm running in time $2^{n^{\epsilon}}$.  See also this cs.stackexchange discussion.  As far as we know, ETH is true.

Define OP$_c$ to be the restriction of the OrderedPartition problem to instances where $d \le \log^c n$.  Equivalently, to instances where $n \ge 2^{d^{1/c}}$.  Here we intend OP$_c$ to capture what the post means by "intermediate instances".  We show that these instances are not likely to be in P, nor NP-hard.

Lemma 1. If OP$_c$ is in P for all $c$, then ETH fails.

Proof.  Suppose OP$_c$ is in P for all $c$.  That is, for some function $f$, OP$_c$ has an algorithm running in time $n^{f(c)}$. SAT inputs of size $n$ reduce (via Partition as described in the post) to OrderedPartition$[2^{n^{b/c}}, n^b]$, for some constant $b$ and any constant $c&gt;0$.  So, SAT inputs of size $n$ reduce to OP$_c$ instances of size $2^{n^{b/c}}$, which can be solved in time $2^{f(c)n^{b/c}}$ via the algorithm for OP$_c$.  For any $\epsilon&gt;0$, taking, say, $c=2b/\epsilon$, SAT can be solved in time $2^{c' n^{\epsilon/2}} \le 2^{n^{\epsilon}}$ (for large $n$), violating ETH.$~~~~\Box$

Note: It seems likely to me that even OP$_2$ is not in P, but showing something like that would be similar to showing, say, that SAT has no algorithm running in time $2^{\sqrt n}$.

Lemma 2. If OP$_c$ is NP-hard for some $c$, then ETH fails.

Proof.  Suppose OP$_c$ is NP-hard for some $c$.  Then SAT inputs of size $n$ reduce to OP$_c$ in time $O(n^b)$ for some $b$.  That is, to instances of OrdereredPartition$[n^b, d]$ where $d\le \log^c (n^b)$.  As observed in the post such instances can be solved in time 
$n^{O(1)} 2^d = n^{O(1)} 2^{\log^c (n^b)}$, (strongly!) violating ETH.$~~~~\Box$

Probably something cleaner or stronger can be shown.  If I had to guess, I'd define NP$_{d(n)}$ to be the complexity class comprised of those languages that have a non-deterministic poly-time algorithm that, on any input of size $n$, uses at most $d(n)$ non-deterministic guesses.  (Here $d$ could be any function.)  Then OrderedPartition$[n, d(n)]$ is in NP$_{d(n)}$.  Perhaps it is complete for that class under poly-time reductions?  A natural guess for a problem that should be complete for the class would be: given a circuit of size $n$ with $d$ input gates, is there an input that makes the circuit output True?  Or something like that.  (I wonder how this compares to, say, defining SAT$_{p(n)}$ to consist of SAT instances, padded with $p(n)$ useless bits to make the input larger.  When $p(n)$ is super-polynomial but sub-exponential, the problem should be neither NP-hard nor in P.)

p.s. See also Consequences of sub-exponential proofs/algorithms for SAT .