3
$\begingroup$

Given a sequence $q_1, \ldots, q_n$ of numbers, decide if the set $I=\{1,\ldots,n\}$ can be partitioned into $k$ sets $I_1, \ldots, I_k$ such that $\sum_{i\in I_1} q_i=\sum_{i\in I_2} q_i = \dots = \sum_{i\in I_k} q_i$.

I know that the problem is NP-hard for $k=2$, strongly NP-hard for $k=3$ already. But are there higher values of $k$, for which they can be provably harder? For example, results like $\Sigma_2^p$-hardness, or $APX$-hardness etc. that are known?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Short answer: It doesn't look like it.

For your first example, hardness results for higher levels of the polynomial hierarchy, this problem is in NP for all $k$ (since a solution can be verified in polynomial time), so we would not expect the problem to be complete for e.g. $\Sigma_2^p$.

For your second example, you must choose some objective function to approximate, so you don't really have one problem anymore. In any case, the Wikipedia page mentions some objective functions, like minimizing the largest sum, that have a PTAS for all $k$. So we wouldn't expect it to be complete for APX either. Although, some natural objective functions (e.g. difference between largest and smallest sum) are not discussed there and you would probably need to do more research to figure out if there are any hardness results for that function.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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