# 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:

1. $$\sum_{i\in I} a_i = \sum_{j\in J} a_i$$
2. 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>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>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>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.)

• Very interesting, thanks! – Erel Segal-Halevi Jul 25 '19 at 5:27