2
$\begingroup$

Why does the definition of the 3-partition problem contain the condition $$\frac{B}{4}<x_i<\frac{B}{2}?$$

I don't understand why leaving out this condition changes the 3-partition problem.

$\endgroup$
1
  • $\begingroup$ What can you deduce about the size of sets that sum to B when each element satisfies that condition? ​ ​ $\endgroup$ – user12859 Mar 2 '16 at 22:08
2
$\begingroup$

The 3-PARTITION problem is NP-complete even without this condition. It is a stronger result that 3-PARTITION is NP-complete even with this condition. The condition presumably comes from the reduction used to prove that 3-PARTITION is NP-hard.

The fact that 3-PARTITION is NP-complete even when all integers are bounded in $(B/4,B/2)$ can be helpful when using 3-PARTITION to prove that other problems are NP-hard.

$\endgroup$

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.