A table wider than its input

The knapsack table has $(n+1)(W+1)$ cells: one row per item, one column per capacity. It is filled in one pass, every cell does constant work, and the whole thing is routinely described as a polynomial-time algorithm for a problem that is otherwise NP-hard.

Every word of that description is true and the conclusion anybody draws from it is wrong.

$n$ is a count of things in the input. $W$ is a number written in the input, and writing a number down takes about $\log_2 W$ characters. So a table proportional to $W$ is a table proportional to $2^{\text{(length of one field)}}$, and adding one bit to the capacity — one character — doubles the work.

The table grew by a factor of 64. The input grew by a factor of 1.47.

What “polynomial time” is a statement about #

The definition is precise and the precision is the whole content: an algorithm runs in polynomial time if its cost is bounded by a polynomial in the length of its input as written down.

Not in the number of items. Not in the largest number appearing. In the number of characters it takes to state the problem.

That is not pedantry, and it is not a definition chosen to be awkward. It is chosen so that the class does not depend on how the input happens to be encoded, which it would if the measure were anything else — and the knapsack table is the standard demonstration that the choice matters. Under a binary encoding of the capacity the algorithm is exponential. Under a unary encoding — $W$ written as $W$ tally marks — the input length is $\Theta(W)$ and the same algorithm is genuinely polynomial in it.

The algorithm did not change. The encoding did, and the class moved.

An algorithm with this behaviour is called pseudo-polynomial: polynomial in the numeric value of the inputs, exponential in their length. The problems that admit one are called weakly NP-hard, and the distinction is real — there are NP-hard problems, such as three-partition, for which no pseudo-polynomial algorithm exists unless P = NP, so the knapsack’s table is a genuine property of the knapsack and not a general escape.

The unit of the capacity is part of the input #

The cleanest way to feel the problem is to change the units and change nothing else.

A knapsack whose capacity is 600 grams and whose weights are in grams has a table 601 columns wide. Express the same physical problem in milligrams — capacity 600,000, weights multiplied by a thousand — and the table has 600,001 columns. The items are the same items, the answer is the same answer, the input is nine characters longer, and the work is a thousand times greater.

Nothing about that is a trick. It is what “proportional to $W$” means, and it is why the same algorithm is entirely practical for a scheduling problem measured in whole days and entirely impractical for the same problem measured in milliseconds. The people who run into this do not run into it by choosing adversarial inputs; they run into it by changing a unit.

The related case is money. A change-making or budgeting problem in whole pounds is a small table; the same problem in pence is a table a hundred times wider; the same problem in a currency with a smaller minor unit is wider still. Every one of those is the same problem to the person posing it.

Where this sits among the site’s other complaints about bounds #

This is the fourth time on this site that a bound has turned out to be a correct statement about something other than what a reader took it for, and the four are worth putting side by side because the failure is the same shape each time.

What O-notation does not say: a class is a statement about a limit, and the constant it drops can be anything. A limit is not a prediction: the crossover between two classes can sit beyond any size that will ever be run. The block that is not a block: a cost model with unstated parameters produces numbers that are correct in the model and meaningless outside it. And here: a bound is polynomial in a quantity that the reader assumes is the size of the input and is not.

In every case the statement is true. In every case what makes it misleading is a quantity that was not named — the constant, the crossover, the parameters, the encoding — and in every case the repair is the same, which is to name it and measure it.

The memo that is not a memo #

There is a second thing that goes wrong on this table and it is a defect rather than a misreading, so it belongs here for a different reason.

Memoising the recursion on the item index alone is a small, natural-looking mistake. The recursion has two arguments; the cache key has one; and the resulting program runs, terminates, and returns a number.

Twelve cells instead of thirteen hundred, and an answer that is 68% too high. It is too high rather than too low, which removes the one sanity check somebody might have applied: an optimisation that returns more than the optimum is obviously wrong to anybody who has the optimum, and to anybody who does not it looks like a very good result.

Nothing inside that program can detect it. There is no invariant to violate, no assertion to fire, and no bound to breach. It is caught only by computing the same quantity a second way — which is why this site’s gate runs both and compares, and why the subproblem in a memo must be the whole state the recurrence branches on rather than the argument that happens to look like an index.

The way out, and it changes the question #

The table’s width is a number from the input. The escape is to make it a number the algorithm chooses.

Index the table by total value rather than by capacity: cell $(i, v)$ holds the least weight needed to reach a value of $v$ using the first $i$ items. That table is $(n+1)(V+1)$ cells with $V$ the total value, which is exactly as bad as before — until the values are rounded.

Divide every value by $\varepsilon \cdot v_{\max} / n$ and take the floor. The rounded values sum to at most $n^2/\varepsilon$, so the table is $O(n^3/\varepsilon)$ cells whatever the numbers in the input were. Each item loses less than the rounding unit, at most $n$ items are taken, so the answer loses at most $\varepsilon \cdot v_{\max} \le \varepsilon \cdot \text{optimum}$.

That is a fully polynomial-time approximation scheme, and the reason it works is worth stating in one line: values can be rounded and capacities cannot. Rounding a value changes how good a solution is said to be; rounding a capacity changes which solutions are legal.

Measured on eight items with six-figure values against a capacity of 600, whose exact optimum is 190,515 and whose exact table is 5,409 cells:

The guarantee permits giving away half the optimum and the scheme gives away one percent. That is the same shape the streaming field measured on a sketch whose bound permitted seven hundred failures and which produced none — the guarantee that is per query — and it carries the same warning. A bound that is loose by a factor of fifty is still a bound, it is still the only thing that holds on every input, and the measured behaviour on one instance is not a licence to assume it.

The gate asserts both directions: the ratio must never fall below $1 - \varepsilon$, and some setting in the sweep must lose something. Without the second half the first would have been verified against an instance where rounding happened to cost nothing, which is a check that fires on nothing.

Both of the alternatives above are worth having in mind while reading the defence, because they change what it is a defence of: not the table, but the decision to reach for it first.

The defence, and what is left of it #

There is a reasonable answer to all of this and it deserves stating properly, because the pseudo-polynomial table is genuinely used and the people using it are not confused.

The defence is that in practice the numbers are small. A knapsack over a few hundred items with a capacity in the thousands is a table of a few hundred thousand cells, which is nothing, and the exponential in the encoding never gets a chance to bite because the encoding never gets long. Under that reading the bound $\Theta(nW)$ is exactly the right thing to quote, because $W$ is a quantity the person posing the problem knows.

What is left of the objection after that is two things and both are practical.

It fails silently and suddenly. The behaviour is linear in $W$ with a small constant right up to the point where the table no longer fits in memory, and then it stops. There is no gradual degradation to warn anybody, and the parameter that crosses the threshold is often not the one being varied — a change of units, a finer-grained resource, a merged data set with one large entry.

The top-down form does not have the problem, on many instances. The reachable capacities are the subset sums of the weights, and there are at most $2^n$ of them but usually far fewer, bounded by the total weight. Measured, the top-down cell count stops growing at 2,157 while the bottom-up one goes on doubling — so on that family of instances the recurrence is not pseudo-polynomial at all and the strategy was what made it so.

That is the more useful conclusion than the taxonomy. The problem is weakly NP-hard and the exact table is exponential in the encoding, and both of those are facts about the worst case; what an implementation actually costs is decided by which capacities its own weights can reach, and that is measurable on the instance in hand.

The other direction the same complaint runs #

There is a mirror image of this defect and it is worth naming, because a reader who has taken the point above will meet it and mistake it for the same thing.

A bound stated in the length of the encoding can be misleading in the opposite direction: an algorithm that is exponential in the length of a number can be entirely practical when that number is small, and an algorithm that is polynomial in the length can be useless when the polynomial has a large degree or a large constant. “Polynomial time” is a class boundary chosen because it is robust to the encoding and to the machine, not because it is a prediction that a program will finish.

This site has made that point before at the other end of the scale — a limit is not a prediction measured a crossover past any size that will ever be run — and the two complaints are the same complaint. A class is a statement about how a cost moves as one stated quantity grows. It is silent about the constant, silent about the range, and silent about which quantity is being grown. Naming that quantity is the whole of the discipline, and it is why every plate on this site prints its own axis.

The other exponential, and choosing between them #

The table is exponential in the length of the capacity field. There is a completely different exact method that is exponential in the number of items and does not contain $W$ at all, and having both turns a lament into a decision.

Split the items into two halves. Enumerate every subset of the first half, recording its weight and value; do the same for the second. Sort one list by weight, and for each subset of the other half find the best-value partner that fits in the remaining capacity. That is about $2^{n/2}$ subsets on each side plus a sort, and its cost mentions no number from the input — only how many items there are.

So the two exact methods are exponential in different things:

and the crossing between them is at roughly $W \approx 2^{n/2}$. Forty items against a capacity of a thousand is a table of forty thousand cells and a subset enumeration of a million: the table wins easily. Forty items against a capacity of a billion is a table of forty billion cells and the same million: the enumeration wins by four orders of magnitude.

Both are exact, both are exponential, and which exponential bites is decided by two numbers the caller has in hand before choosing. That is a much better position than the one the pseudo-polynomial framing suggests, where the table is presented as the dynamic-programming answer and the alternative is not mentioned.

It also sharpens what “weakly NP-hard” is telling anybody. It says a pseudo-polynomial algorithm exists — not that it is the one to run. On an instance with few items and enormous numbers the pseudo-polynomial algorithm is the slow one, and the method with the frankly exponential bound is the practical choice.

Capacities can be rounded, if overfilling is allowed #

The rule stated above — values can be rounded and capacities cannot — is exactly right for the problem as posed, and it is worth noticing what happens when the posing is relaxed.

Rounding a capacity changes which solutions are legal, so an algorithm that rounds it returns a solution that may not fit. If the constraint is physical — a container, a vehicle, a page — that is a wrong answer and there is nothing more to say. If the constraint is a budget, a quota or a time allowance, a solution that exceeds it by a stated fraction may be perfectly acceptable, and then the capacity axis can be scaled exactly as the value axis is.

That gives a bicriteria approximation: within $\varepsilon$ of the optimal value, using at most $(1+\varepsilon)$ of the capacity, with a table whose width no number in the input can move. It is a weaker guarantee in one dimension and a stronger one in another, and which of the three schemes to use is settled by a question about the application rather than about the algorithm.

Naming it is worth a paragraph because of the pattern rather than the technique. A resource that cannot be approximated is often a resource whose constraint was stated more strictly than the situation required, and the question “what happens if this bound is exceeded by one per cent” is worth asking before concluding that an axis is untouchable.

What to take from it #

Three things, and none of them is about the knapsack.

Name the $n$. A bound is a function of something, and on this site every plate says what. “Polynomial in $n$ and $W$” is a complete statement and “polynomial” is not, and the gap between them is where the whole of this essay lives.

A table’s dimensions come from the state, and the state can be chosen. Capacity and total value index the same problem, they are both correct, and one of them has an axis that can be rounded. Recognising that a recurrence has more than one possible state is the move that produced the approximation scheme, and it is not visible from a bound.

A cheaper answer with no way to check it is not cheaper. The index-only memo is 109 times smaller than the correct table and it is not an optimisation, it is a different function. The site’s method here is the one it applies everywhere: compute the same quantity by machinery that does not share the mistake, and compare.