3
$\begingroup$

I'm a bit confused about the 3-partition problem. More specifically I'm confused about this from the Wikipedia article:

Let B denote the (desired) sum of each subset Si, or equivalently, let the total sum of the numbers in S be m B. The 3-partition problem remains strongly NP-complete when every integer in S is strictly between B/4 and B/2.

Does this mean that if the multiset contains elements that fall outside the range B/4-B/2 the problem is no longer strongly NP-complete and admits heuristics or other optimizations? Am I interpreting that right?

Also am I correct in assuming that this problem (at least when it is strongly NP-complete) pretty much requires an exhaustive search (unless P=NP)?

I've sifted through some papers but haven't been able to figure this out.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

No. Intuitively, the problem gets harder if we take out the restrictions on the input values, since the restricted instances are a subset of the instances of the general problem. However, the article says, even if you introduce this restriction the problem does not get easier and it is still strongly NP-complete.

On the other hand, exhaustive search is not always the best approach for hard problems. Parameterized algorithm introduce methods usually to restrict the area where the exhaustive search must happen. Randomized algorithm offer methods where a greedy algorithm or a heuristic looking among bounded number of solutions gives an optimal answer with some probability. repeating the method enough number of times yield an answer with high probability. So no it does not mean that an exponential exhaustive method on the whole input is the best we can do. It only means unless $P = NP$, no polynomial time deterministic non-randomized algorithm can be designed for this problem.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Not really. The best I can tell is the polynomial kernel for the d-set packing which is a generalization of 3d-matching which is a generalization (actually equivalent) to set partitioning. The problem is that even though the running time is polynomial in $n$ (due to reduction rules) it is polynomial in $k$ which is the size of the output. In our case we are looking for a perfect matching and hence $k = n/3$ so this result does not help here. $\endgroup$
    – Narek Bojikian
    Commented Nov 16, 2019 at 3:10
  • 1
    $\begingroup$ For more infos about this kernel check "Parameterized Algorithms" book by Cygan et. al. $\endgroup$
    – Narek Bojikian
    Commented Nov 16, 2019 at 3:10
  • 1
    $\begingroup$ Thanks. I didn't mention it but what I'm looking for here is actually a "reliably slow" problem for applications like a randomness beacon or password hashing. It wouldn't be used directly for crypto but within a construct to make brute forcing impractical. There are other functions of course like ModSqrt, balloon hashing, huge memory lookup tables, forcing a large in-memory sort, etc., but I'm just looking for simpler or novel alternatives. This one is neat because it seems reliably slow yet trivially verifiable (check to see if the sets add to the same value). $\endgroup$
    – Adam Ierymenko
    Commented Nov 17, 2019 at 0:03
  • 1
    $\begingroup$ But then you should make sure that the generated instances are hard, i.e. do not all belong to a strict case or have something in common that makes the problem easy. For instance, I mentioned that even if each word is one letter it is hard. However, if every sentence is one word you can solve it greedily if sentences do not repeat and with dynamic programming if they do. So just make sure to build general hard instances with alphabet/sentences/words big enough. $\endgroup$
    – Narek Bojikian
    Commented Nov 17, 2019 at 10:21
  • 1
    $\begingroup$ Input would be random (hashes, etc.) so the average case is what matters. A heuristic that speeds up some cases wouldn't help much, especially if it slows down others. No way to bias the input as it would be output from a cryptographic hash or cipher. $\endgroup$
    – Adam Ierymenko
    Commented Nov 19, 2019 at 16:40

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.