3-partition problem: Difference between revisions

Revision as of 22:02, 18 November 2020

Revision as of 22:02, 18 November 2020

Line 17:

== 3-Partition vs Partition ==

The 3-partition problem is similar to the [[partition problem]], in which the goal is to partition ''S'' into two subsets with equal sum, and the [[multiway number partitioning]], in which the goal is to partition ''S'' into ''k'' subsets with equal sum, where ''k'' is a fixed parameter. In 3-Partition the goal is to partition ''S'' into ''m'' = ''n''/3 subsets, not just a fixed number of subsets, with equal sum. Partition is "easier" than 3-Partition: while 3-Partition is [[strongly NP-hard]], Partition is only [[Weak NP-completeness|weakly NP-hard]] - it is hard only when the numbers are encoded in non-unary system, and have value exponential in ''n''. When the values are polynomial in ''n'', Partition can be solved in polynomial time (using athe [[Pseudo-polynomial time|pseudopolynomial time number partitioning]] algorithm).

==Variants==