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:
“All of us recognize the great benefits to our own nation and to the world of a strong and progressive Iran. Your support of the Camp David accords and your encouragement of the leaders who are or may be involved in consummating the peace effort would be very valuable.”
—Jimmy Carter (James Earl Carter, Jr.)