skip to content

Partition asks whether parcel weights split evenly between two trucks; why doesn't an O(n*T) table over totals put it in P?

level: middleimportance: must knowfreq 62%

answer

  1. cost is measured in input length
  2. weights are values, not sizes
  3. one more digit, ten times wider
  4. polynomial in magnitude, not in length
  5. pseudo-polynomial: Partition stays NP-complete

basics

~10 s

An O(n*T) table is pseudo-polynomial: T is a numeric value carried by only about log T digits, so the table is exponential in the instance's written length, not polynomial in it.

solid answer

~40 s

Polynomial time is measured against the **length** of the input, not the values inside it. A Partition instance is `n` weights written as numerals, so a weight of one million costs seven characters, not a million. The weight-indexed sweep does work proportional to `n * T`, where `T` is the sum of the weights - a value, and a value is exponential in its own digit count. Add one decimal digit to every weight and the instance grows by `n` characters while the table grows about tenfold. That is what pseudo-polynomial means: polynomial in the numeric magnitude, exponential in the encoded length. Partition stays NP-complete, and the table is a perfectly good algorithm on instances whose numbers are small.

code

pseudocode · 13 lines
pseudocode
n = count of parcels
T = sum of parcel weights
table_cells = n * T          # work done by the weight-indexed sweep

instance_length = 0
for each w in parcels:
    instance_length = instance_length + digit_count(w)

# now write one extra digit on every weight:
#   instance_length grows by n characters
#   every w grows about tenfold, so T grows about tenfold
#   table_cells grows about tenfold
# tenfold work for n extra characters is not polynomial growth

go deeper

for a junior

Recall that an algorithm's cost is judged against how long the input is to write down, and that a big number is short to write. A weight of one million is seven characters.

for a middle

Explain the mechanics: the sweep touches n times T cells, T is a value rather than a count, and adding one digit to every weight multiplies the table tenfold while the instance grows by n characters.

for a senior

Show the judgment: decide from a real instance whether the numbers are bounded by a polynomial in the item count, and say what would break the choice - a unit change or a precision change, not a bigger fleet.

for a principal

Frame the tradeoff for others: a method whose cost tracks numeric precision couples an algorithm's budget to a data-modelling decision, and that coupling belongs in the design review, not in a later incident.

## Polynomial in what? An algorithm runs in **polynomial time** when its step count is bounded by a polynomial in the **length of its input**: the number of characters, or bits, needed to write the instance down. That is the only yardstick the class **P** uses, and it is why a Partition instance has to be looked at twice. A Partition instance is a list of `n` parcel weights, and each weight is written as a numeral. A weight of one million occupies seven characters, not one million characters. The length of the whole instance is therefore roughly `n` times the digit count of a typical weight - a few thousand characters for a realistic manifest, however heavy the parcels happen to be. ## Where the table's work actually goes The weight-indexed sweep keeps one entry for every running total from `0` up to `T`, the sum of all the weights, and refreshes that row of entries once per parcel. Its work is proportional to `n * T`, and the two factors are completely different kinds of quantity: - `n` is a **count of things present** in the instance, so it is bounded by the instance's length. - `T` is a **value read off** the instance. A value is exponential in its own digit count: `d` decimal digits express numbers up to ten to the power `d`. That asymmetry is the whole story. Add one decimal digit to every weight and the instance grows by `n` characters - a rounding error - while `T`, and with it the table, grows roughly tenfold. | largest weight | digits per weight | instance length (n = 200) | T at most | cells (n * T) | |---|---|---|---|---| | 1,000 | 4 | about 800 characters | 200,000 | 4 x 10^7 | | 1,000,000 | 7 | about 1,400 characters | 2 x 10^8 | 4 x 10^10 | | 10^12 | 13 | about 2,600 characters | 2 x 10^14 | 4 x 10^16 | The instance roughly triples in length; the table grows by nine orders of magnitude. No polynomial in the first column's length behaves like that. ## Pseudo-polynomial, precisely An algorithm is **pseudo-polynomial** when its running time is bounded by a polynomial in the item count and in the **numeric magnitude** of the numbers in the instance, rather than in the length of those numbers. Four things worth being exact about: - It is a real complexity claim with a definition, not a hedge or an apology for a slow constant. - It does not mean 'almost polynomial' or 'polynomial for practical purposes'. The gap between magnitude and length is exponential, not constant. - It is a property of the **algorithm on a family of instances**, not of the problem. Partition is NP-complete whatever algorithm you point at it. - The very same table is honestly polynomial on any family whose numbers are bounded by a polynomial in the item count, because then `T` itself is bounded by a polynomial in `n`. ## Why the classification is untouched Partition is NP-complete. An algorithm polynomial in the **instance length** would place an NP-complete problem in P and so prove P = NP, which nobody has done. The table does not do that, because its cost is polynomial in a value rather than in a length, so the classification is left exactly where it was. Two things this argument does **not** say: - It does not say Partition requires exponential time. No such lower bound is known; the open question is open in both directions. All the argument establishes is that *this* algorithm is not the polynomial one. - It does not say the table is a bad choice. On instances with small weights it is the right tool and beats subset search comfortably. ## The test to run on your own instance 1. Find the largest number a realistic instance actually carries, and the count of items. 2. Ask whether that largest number is bounded by a small constant, or by a polynomial in the item count. Quantised things - shelf slots, pallet positions, staff counts - usually are. 3. If it is, the value-indexed table is genuinely polynomial on your instances and the pseudo-polynomial label is a technicality you can ignore. 4. If instead the numbers carry precision - currency in minor units, masses in grams, timestamps - then the table's width is set by that precision and not by the size of your business, and it will be the precision that breaks you. The habit to build is to look at the **largest number** in the instance whenever you see a cost like `n * T`, and ask what that number would be if someone changed a unit. Loop nesting tells you nothing here; the magnitude of the index does.

  • What would a genuinely polynomial algorithm for Partition have to be polynomial in?
    In the item count and the total number of digits used to write the weights - the instance's length. No such algorithm is known, and since Partition is NP-complete, producing one would prove P = NP. That is the bar the weight-indexed table does not clear.
  • If every parcel weight is capped at 50 units, is the table polynomial then?
    Yes. The total is then at most 50 times the item count, so the table has at most about 50n^2 cells - polynomial in the instance length. Bounding the values by a polynomial in the item count is exactly what turns a pseudo-polynomial algorithm into a polynomial one on that restricted family.
  • Does the same objection apply to a cost of n times the number of distinct weights?
    No. The count of distinct weights is bounded by the item count, so it is a count and not a magnitude; a cost in terms of it is polynomial in the instance length. The objection only bites when a loop is indexed by a number the input names rather than by things the input contains.

Think of a filing cabinet with one drawer per possible total weight. Writing one more digit on every label does not add a drawer or two - it makes the cabinet ten times longer, while the labels themselves barely grew.

saying these in an interview costs you the question

  • Claims the weight-indexed table proves Partition is in P
  • Treats the numeric total T as if it were the input size
  • Counts two nested loops and concludes polynomial time
  • Reads pseudo-polynomial as a slightly slower flavour of polynomial
  • Concludes the table is useless even when weights are small
  • Says Partition has been proved to need exponential time