World's most popular travel blog for travel bloggers.

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

, , No Comments
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.

Asked By : Franz
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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53914

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback