3-partition Problem - Strong NP-completeness

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:

    Let those possess the land, and only those,
    Who love it with a love so strong and stupid
    That they may be abused and taken advantage of
    And made fun of by business, law, and art....
    Robert Frost (1874–1963)