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:
““Would you—be good enough—” Alice panted out, after running a little further, “to stop a minute—just to get—one’s breath again?”
“I’m good enough,” the King said, “only I’m not strong enough. You see, a minute goes by so fearfully quick. You might as well try to stop a Bandersnatch!””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)