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:
“Methinks I see in my mind a noble and puissant nation rousing herself like a strong man after sleep, and shaking her invincible locks. Methinks I see her as an eagle mewing her mighty youth, and kindling her undazzled eyes at the full midday beam.”
—John Milton (1608–1674)