patternMinor
Conditions under which the 3-partition problem is not strongly NP-complete?
Viewed 0 times
problemthepartitionstronglyundercompleteconditionswhichnot
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#117154, answer score: 2
Revisions (0)
No revisions yet.