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:
“... but by that time a lot of sea had rolled by and Lucette was too tired to wait. Then the night was filled with the rattle of an old but still strong helicopter. Its diligent beam could spot only the dark head of Van, who, having been propelled out of the boat when it shied from its own sudden shadow, kept bobbing and bawling the drowned girl’s name in the black, foam-veined, complicated waters.”
—Vladimir Nabokov (1899–1977)