<p>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.</p>

<p>Note: The <a href="https://en.wikipedia.org/wiki/Exponential_time_hypothesis" rel="noreferrer">Exponential-Time Hypothesis</a>, or ETH, is that it is not the case that, for every constant <span class="math-container">$\epsilon&gt;0$</span>, SAT has an algorithm running in time <span class="math-container">$2^{n^{\epsilon}}$</span>.  See also <a href="https://cs.stackexchange.com/questions/9813/are-there-subexponential-time-algorithms-for-np-complete-problems">this</a> cs.stackexchange discussion.  As far as we know, ETH is true.</p>

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

<p><strong>Lemma 1.</strong> <em>If OP<span class="math-container">$_c$</span> is in P for all <span class="math-container">$c$</span>, then ETH fails.</em></p>

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

<p>Note: It seems likely to me that even OP<span class="math-container">$_2$</span> is not in P, but showing something like that would be similar to showing, say, that SAT has no algorithm running in time <span class="math-container">$2^{\sqrt n}$</span>.</p>

<p><strong>Lemma 2.</strong> <em>If OP<span class="math-container">$_c$</span> is NP-hard for some <span class="math-container">$c$</span>, then ETH fails.</em></p>

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

<p>Probably something cleaner or stronger can be shown.  If I had to guess, I'd define NP<span class="math-container">$_{d(n)}$</span> to be the complexity class comprised of those languages that have a non-deterministic poly-time algorithm that, on any input of size <span class="math-container">$n$</span>, uses at most <span class="math-container">$d(n)$</span> non-deterministic guesses.  (Here <span class="math-container">$d$</span> could be any function.)  Then OrderedPartition<span class="math-container">$[n, d(n)]$</span> is in NP<span class="math-container">$_{d(n)}$</span>.  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 <span class="math-container">$n$</span> with <span class="math-container">$d$</span> 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<span class="math-container">$_{p(n)}$</span> to consist of SAT instances, padded with <span class="math-container">$p(n)$</span> useless bits to make the input larger.  When <span class="math-container">$p(n)$</span> is super-polynomial but sub-exponential, the problem should be neither NP-hard nor in P.)</p>

<p>p.s. See also <a href="https://cstheory.stackexchange.com/questions/9237/consequences-of-sub-exponential-proofs-algorithms-for-sat">Consequences of sub-exponential proofs/algorithms for SAT</a> .</p>

CC BY-SA 4.0
2019-07-25T05:27:06.887Z
Very interesting, thanks!
Erel Segal-Halevi
CC BY-SA 4.0
2019-07-24T03:39:42.500Z
2019-07-24T03:52:57.377Z
2019-07-24T03:52:57.377Z
Neal Young
<p>In the <code>OrderedPartition</code> problem, the input is two sequences of <span class="math-container">$n$</span> positive integers, <span class="math-container">$(a_i)_{i\in [n]}$</span> and <span class="math-container">$(b_i)_{i\in [n]}$</span>.
The output is a partition of the indices <span class="math-container">$[n]$</span> into two disjoint subsets, <span class="math-container">$I$</span> and <span class="math-container">$J$</span>, such that:</p>

<ol>
<li><span class="math-container">$\sum_{i\in I} a_i = \sum_{j\in J} a_i$</span></li>
<li>For all <span class="math-container">$i\in I$</span> and for all <span class="math-container">$j\in J$</span>: <span class="math-container">$b_i\leq b_j$</span>.</li>
</ol>

<p>In other words, we have to first order the indices on a line such that the <span class="math-container">$b_i$</span> are weakly increasing, and then cut the line such that the sum of the <span class="math-container">$a_i$</span> in both sides is the same.</p>

<p>If all <span class="math-container">$b_i$</span> are the same, then condition 2 is irrelevant and we have an instance of the NP-hard <code>Partition</code> problem.
On the other hand, if all <span class="math-container">$b_i$</span> are different, then condition 2 imposes a single ordering on the indices, so there are only <span class="math-container">$n-1$</span> options to check, and the problem becomes polynomial. What happens in between these cases?</p>

<p>To formalize the question, define by <code>OrderedPartition[n,d]</code>, for <span class="math-container">$1\leq d\leq n$</span>, 
the problem restricted to instances of size <span class="math-container">$n$</span>, in which the largest subset of identical <span class="math-container">$b_i$</span>-s is of size <span class="math-container">$d$</span>. So the easy case,  when all <span class="math-container">$b_i$</span>-s are different, is <code>OrderedPartition[n,1]</code>, and the hard case, when all <span class="math-container">$b_i$</span>-s are identical, is <code>OrderedPartition[n,n]</code>. </p>

<p>More generally, For any <span class="math-container">$n$</span> and <span class="math-container">$d$</span>, in any <code>OrderedPartition[n,d]</code> instance, the number of possible partitions respecting condition 2 is <span class="math-container">$O(n 2^d)$</span>. Hence, if <span class="math-container">$d\in O(\log{n})$</span>, then <code>OrderedPartition[n,d]</code> is still polynomial in <span class="math-container">$n$</span>. </p>

<p>On the other hand, for any <span class="math-container">$n$</span> and <span class="math-container">$d$</span>, we can reduce from a <code>Partition</code> problem with <span class="math-container">$d$</span> integers to <code>OrderedPartition[n,d]</code>. Let <span class="math-container">$p_1,\ldots,p_d$</span> be an instance of <code>Partition</code>. Define an instance of <code>OrderedPartition[n,d]</code> by:</p>

<ul>
<li>For each <span class="math-container">$i\in \{1,\ldots,d\}$</span>, let <span class="math-container">$a_i := 2n\cdot p_i$</span> and <span class="math-container">$b_i := 1$</span>.</li>
<li>For each <span class="math-container">$i\in \{d+1,\ldots,n\}$</span>, let <span class="math-container">$a_i := 1$</span> and <span class="math-container">$b_i := i$</span><br>
<sub>[if <span class="math-container">$n-d$</span> is odd, make <span class="math-container">$a_n:=2$</span> such that the sum will be even]</sub>.</li>
</ul>

<p>Hence, if <span class="math-container">$d\in\Omega(n^{1/k})$</span>, for any integer <span class="math-container">$k\geq 1$</span>, then <code>OrderedPartition[n,d]</code> is NP-hard.</p>

<p>QUESTION: What happens in the intermediate cases, in which <span class="math-container">$d$</span> is super-logarithmic but sub-polynomial in <span class="math-container">$n$</span>?</p>

<np-hardness><partition-problem>
A partition problem with order constraints
Erel Segal-Halevi
# A partition problem with order constraints

(Asked by: username_0 on 2019-07-15)

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$?

**Tags:** np-hardness, partition-problem

---

## 1 answers

### Answer by username_1 on 2019-07-24. Score: 5 | Accepted answer

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](https://en.wikipedia.org/wiki/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](https://cs.stackexchange.com/questions/9813/are-there-subexponential-time-algorithms-for-np-complete-problems) 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.)

p.s. See also [Consequences of sub-exponential proofs/algorithms for SAT](https://cstheory.stackexchange.com/questions/9237/consequences-of-sub-exponential-proofs-algorithms-for-sat) .

> **Comments:**
> **username_0**: Very interesting, thanks!  

---

