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:
“It’s important for parents to watch for trouble and convey to their daughters that, if it comes, they are strong enough to deal with it. Parents who send their [adolescent] daughters the message that they’ll be overwhelmed by problems aren’t likely to hear what’s really happening.”
—Mary Pipher (20th century)