8
$\begingroup$

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

$\endgroup$
5
+50
$\begingroup$

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.)

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

$\endgroup$
  • $\begingroup$ Very interesting, thanks! $\endgroup$ – Erel Segal-Halevi Jul 25 at 5:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.