Strong NP-completeness
The 3-partition problem remains NP-complete even when the integers in S are bounded above by a polynomial in n. In other words, the problem remains NP-complete even when representing the numbers in the input instance in unary. i.e., 3-partition is NP-complete in the strong sense or strongly NP-complete. This property, and 3-partition in general, is useful in many reductions where numbers are naturally represented in unary. In contrast, the partition problem is known to be NP-complete only when the numbers are encoded in binary, and have value exponential in n.
Read more about this topic: 3-partition Problem
Famous quotes containing the word strong:
“It is a mighty error to suppose that none but violent and strong passions, such as love and ambition, are able to vanquish the rest. Even idleness, as feeble and languishing as it is, sometimes reigns over them; it usurps the throne and sits paramount over all the designs and actions of our lives, and imperceptibly wastes and destroys all our passions and all our virtues.”
—François, Duc De La Rochefoucauld (1613–1680)