skip to content

Capping every parcel weight at a small constant makes Subset Sum easy but leaves 3-Partition hard; what distinction is that?

level: seniorimportance: nice to knowfreq 27%

answer

  1. where does the difficulty actually live
  2. bound every number, ask again
  3. unary numbers as the equivalent test
  4. strong hardness forbids a pseudo-polynomial table
  5. 3-Partition and Bin Packing are strongly hard

basics

~20 s

Weak versus strong NP-hardness. A strongly NP-hard problem stays hard even when every number is bounded by a polynomial in the instance length; a weakly hard one collapses to a value-indexed table once its numbers are small.

solid answer

~40 s

A problem is **strongly NP-hard** when it remains NP-hard on instances whose numbers are all bounded by a polynomial in the instance's length - equivalently, when the numbers are written out in unary. Subset Sum, Partition and Knapsack fail that test: bound their values and the weight-indexed table becomes genuinely polynomial, so they are only **weakly** NP-hard, and their difficulty lives in the magnitude of the numbers. 3-Partition and Bin Packing pass it: they stay hard with tiny item sizes, so their difficulty is combinatorial. The practical consequence is sharp - unless P = NP, a strongly NP-hard problem admits no pseudo-polynomial algorithm at all, so shrinking the numbers is not a strategy for it.

go deeper

for a junior

Recall that two problems can both be hard for different reasons: one because its numbers are huge, one because of how the items must be grouped, and the two respond differently to small numbers.

for a middle

Explain the test itself: bound every number by a polynomial in the instance length and ask whether the problem is still hard. Subset Sum stops being hard, Bin Packing does not.

for a senior

Show the consequence on a plan: a value-indexed method is worth building only on the weak side, and for a strongly hard problem chasing one would amount to settling P versus NP.

for a principal

Use it to steer effort: classify a new requirement by where its difficulty lives before any method is chosen, so the team is not spending sprints on a direction that is provably closed.

## Two different places difficulty can live Two problems can both be NP-hard and still fail for different reasons. In one, the numbers are doing the work: a small instance with enormous values is the hard case. In the other, the arrangement is doing the work: the instance is hard even when every number in it is tiny. The vocabulary that separates them is **weak** versus **strong** NP-hardness, and it is the reason two members of the same catalogue respond completely differently to the same intervention. ## The definition A problem is **strongly NP-hard** if it stays NP-hard when restricted to instances in which every number is bounded by a polynomial in the length of the instance. The equivalent phrasing is that it stays hard when the numbers are written in unary, since a unary number's length is its value and a polynomial bound on the value is then a polynomial bound on the length. A problem that is NP-hard but loses its hardness under that restriction is **weakly NP-hard**, sometimes called NP-hard in the ordinary sense only. The consequence that makes the distinction worth knowing: - **Unless P = NP, a strongly NP-hard problem has no pseudo-polynomial algorithm.** If it had one, bounding the numbers by a polynomial in the instance length would make that algorithm run in polynomial time on instances that are still NP-hard, which would put an NP-hard decision problem in P. - Symmetrically, an existing pseudo-polynomial algorithm is itself a proof that the problem is **not** strongly NP-hard. ## Where the catalogue's numeric problems fall | problem | bound every number by a polynomial in the instance length | verdict | |---|---|---| | Subset Sum, Partition | the value-indexed table becomes polynomial | weakly NP-hard | | Knapsack (decision form) | the value-indexed table becomes polynomial | weakly NP-hard | | 3-Partition | still NP-hard | strongly NP-hard | | Bin Packing | still NP-hard | strongly NP-hard | | Travelling Salesman (decision form) | still NP-hard with only two distinct distances | strongly NP-hard | 3-Partition is the standard witness on the strong side. It asks whether `3m` positive numbers, each strictly between a quarter and a half of the target `B` and summing to `m` times `B`, can be split into `m` triples that each sum exactly to `B`. The size restriction forces every group to hold exactly three items, and the problem stays NP-hard even when all the numbers are bounded by a polynomial in the item count - which is exactly why it is the usual source for hardness proofs about packing and scheduling. ## What this changes about your plan The distinction is not decoration; it decides which responses are even on the table. 1. **Measure the numbers first.** Look at the largest number a real instance carries and compare it with the item count. If the numbers are quantised and small - shelf slots, crates, staff - you may be on the weak side in practice. 2. **Try the cap as a thought experiment.** Ask what happens to your problem if every number in it is replaced by something bounded by a polynomial in the item count. If the problem dissolves, a value-indexed method is worth building. If it is plainly still hard, that direction is closed. 3. **Do not shop for a pseudo-polynomial algorithm for a strongly hard problem.** Not because none has been found, but because finding one would settle P versus NP. Recognising that saves a sprint. ## The trap it protects against The trap is inheritance by association. Subset Sum, Bin Packing and 3-Partition sit in the same list, so it is tempting to assume that what works for one works for all of them. It does not: the value-indexed sweep that makes Subset Sum comfortable on small numbers has no counterpart for Bin Packing, because Bin Packing is hard even when every item size is a single small integer. The reverse error appears too - concluding that a problem with small numbers must be easy. Small numbers only help when the difficulty was numeric to begin with. A packing instance whose item sizes are all between 1 and 6 can still be hard, because what has to be searched is the grouping, not the arithmetic. ## Saying it precisely in an interview The compact form is: `Subset Sum is only weakly NP-hard, so its pseudo-polynomial table is polynomial once the values are bounded by a polynomial in the item count; Bin Packing and 3-Partition are strongly NP-hard, so no such table can exist for them unless P = NP.` That single sentence carries the definition, the consequence and the catalogue placement, and it is the answer the question is fishing for.

  • Why does an existing pseudo-polynomial algorithm rule out strong NP-hardness?
    Because bounding every number by a polynomial in the instance length would make that algorithm polynomial in the instance length. If the problem were still NP-hard under that bound, an NP-hard decision problem would sit in P, so the existence of the algorithm and strong hardness cannot both hold unless P = NP.
  • Why does the definition mention numbers written in unary?
    Because a unary number's written length equals its value, so writing the numbers in unary is exactly the same restriction as bounding their values by a polynomial in the instance length. It is a way of stating the condition without referring to the encoding of each number separately.
  • Is a problem with no numbers in its input strongly or weakly NP-hard?
    Strongly, trivially: a purely structural instance such as a graph has nothing to bound, so the restriction to small numbers leaves the problem untouched and it remains as hard as it was. The distinction is only informative for problems whose instances carry magnitudes.

One puzzle is hard because the numbers printed on the pieces are enormous; another is hard because of how the pieces have to be grouped. Shrink every printed number and only the first puzzle collapses - the second one's difficulty was never in the digits.

saying these in an interview costs you the question

  • Assumes every problem in the catalogue has a pseudo-polynomial table
  • Concludes small item sizes make a packing instance easy
  • Treats strong hardness as simply meaning harder in practice
  • Says a pseudo-polynomial algorithm can coexist with strong hardness
  • Thinks unary encoding is about storage rather than instance length