World's most popular travel blog for travel bloggers.

# 3-partition problem: why $b/4 < x_i < b/2$?

, ,
Problem Detail:

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.

###### Answered By : Yuval Filmus

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.