# Conditions under which the 3-partition problem is not strongly NP-complete?

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.

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.
• 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. Nov 16 '19 at 3:10