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:
“He is a strong man who can hold down his opinion. A man cannot utter two or three sentences, without disclosing to intelligent ears precisely where he stands in life and thought, namely, whether in the kingdom of the senses and the understanding, or, in that of ideas and imagination, in the realm of intuitions and duty.”
—Ralph Waldo Emerson (1803–1882)