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:
“I am the kind of a woman that likes to move on mentally from point to point, and I like for my man to be there way ahead of me. Then if he is strong and honest, it goes on from there. Good looks are not essential, just extra added attraction.”
—Zora Neale Hurston (1891–1960)