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:
“Royalty is a government in which the attention of the nation is concentrated on one person doing interesting actions. A Republic is a government in which that attention is divided between many, who are all doing uninteresting actions. Accordingly, so long as the human heart is strong and the human reason weak, Royalty will be strong because it appeals to diffused feeling, and Republics weak because they appeal to the understanding.”
—Walter Bagehot (1826–1877)