Under what condition on its numbers does a routine whose cost tracks their magnitude still run in polynomial time?
answer
- close the gap between written and large
- the rescue is a promise about inputs
- values bounded by a polynomial in n
- a constant cap is polynomial but useless
- label names the algorithm, not the problem
basics
~20 sWhen the magnitudes themselves are bounded by a polynomial in the input length. Then cost proportional to the value is cost proportional to a polynomial in n, and the routine is genuinely polynomial-time rather than merely pseudo-polynomial.
solid answer
~40 sA magnitude-driven routine is exponential in the input length only because a `d`-digit number can be as large as `10^d`. Remove that freedom and the exponential disappears: if every value in the instance is bounded by some fixed polynomial in the input length `n` — say the amounts can never exceed the number of records — then the work is polynomial in `n` by definition, and the label *pseudo-polynomial* no longer applies. What does **not** qualify is a bound that is merely a large constant, such as 'every amount fits in a fixed-width machine word'. That is formally a constant factor and formally polynomial, while being a factor of billions, which is useless as a defence. The label describes an algorithm against an encoding; it is not a verdict on the problem.
go deeper
Remember the shape of the escape hatch: cost that grows with a number is fine when that number cannot be much bigger than the input itself, and dangerous when it can be astronomically bigger.
State the condition precisely — the largest value bounded by a polynomial in the input length — and be able to show why that turns a magnitude-driven cost into an ordinary polynomial one.
In review, separate a magnitude bound that is a domain rule from one that is an accident of current data, and reject a fixed storage-width cap as a complexity argument even though it technically satisfies the definition.
The call you own is whether to encode the magnitude bound as an enforced invariant. If the cheap algorithm is only correct on bounded magnitudes, that bound belongs in the contract and the validation, not in a comment or a habit.
## Where the exponential actually comes from A routine whose step count tracks the numeric values it is handed is exponential in the input length for one reason only: positional notation lets a short description denote an enormous value. `d` digits buy a magnitude up to about `10^d`. The exponential is not in the code; it is in the gap between how a number is written and how large it is allowed to be. That framing tells you exactly where to intervene. Close the gap and the exponential closes with it. ## The condition that rescues the bound Let `n` be the input length and `V` the largest magnitude appearing in the instance. A routine costing about `n * V` steps is polynomial in `n` precisely when `V` is bounded by some fixed polynomial in `n`. Then `n * V` is at most `n * n^j`, which is a polynomial, and the class question is settled — on that family of instances the algorithm is polynomial-time, full stop, not 'nearly' or 'effectively'. The condition is a statement about the **family of instances**, not about one file. Asymptotic classification quantifies over arbitrarily large inputs, so the promise must be one that holds as the inputs grow. ## Three ways the bound gets claimed, and one that only pretends 1. **The magnitudes are genuinely tied to the instance size.** Amounts expressed in whole units of a currency where the count of units cannot exceed the count of line items; scores bounded by the number of players; positions bounded by the length of the sequence. Here `V` really is at most a polynomial in `n`, and the claim is sound. 2. **The numbers arrive in a notation as long as they are large.** If magnitudes are supplied as counts of units rather than in positional form, the input length already contains `V`, so cost proportional to `V` is cost proportional to `n`. This is a real statement about where the difficulty lives, though it is not a claim about ordinary positional input. 3. **The magnitudes are capped by a fixed constant** — 'no amount exceeds what a fixed-width word holds'. Formally this makes `V` a constant and the bound `O(n)` with a constant factor. It is technically polynomial and practically worthless: a constant factor of billions consumes any machine you own. Treating this as a passing grade is the most common way the condition gets abused. ## The same three cases, side by side | instance family | bound on the largest value | verdict | |---|---|---| | values at most the number of records | polynomial in n | honestly polynomial-time | | values supplied as counts of units | already inside n | polynomial in that input length | | values capped by a fixed wide word | a very large constant | formally polynomial, operationally hopeless | | values as large as the digits permit | exponential in n | not polynomial time | ## What the pseudo-polynomial label does not tell you - **It is not a grade of the problem.** The label attaches to one algorithm under one encoding. Another algorithm for the same problem may be polynomial, and the problem's own difficulty is a separate question decided by other means. - **It is not 'almost polynomial'.** The prefix marks a different measurement, not a near miss. Polynomial in the value and polynomial in the length are different claims, and only the second is the class. - **It is not a verdict on usefulness.** A magnitude-driven algorithm can be the correct engineering choice when the magnitudes in your domain are small, and it is a bad choice the moment someone widens the field that holds them. - **It does not travel with the code.** The same algorithm changes verdict when the instance family changes, because the verdict was always a joint statement about the algorithm and the inputs it is promised. ## The judgment this leaves you with When someone defends a magnitude-driven routine, the question to ask is which of the three cases they are in, and whether the bound on magnitudes is a rule of the domain or an accident of current data. A rule — 'quantities are counts of items and there are at most `n` items' — is a design you can rely on and should write down. An accident — 'nothing has ever exceeded a few thousand' — is a bound that will be revised by whoever adds the next feature, and when it is revised the cost curve does not degrade gracefully: it changes shape.
- Why is 'all amounts fit in a fixed-width word' a weak defence?Because it makes the magnitude a constant rather than a polynomial in the input length. The bound is then formally linear in the number of records with a constant factor in the billions, which satisfies the definition while guaranteeing nothing operationally. A useful bound ties the magnitudes to the instance size, not to a storage width.
- Does the condition have to hold for the whole problem, or only for the instances you meet?Classification is over the family of instances, so a class claim needs the bound to hold as inputs grow. Restricting to a family where magnitudes are polynomially bounded is legitimate, but then the claim is about that restricted family and must be stated that way, not as a claim about the general problem.
saying these in an interview costs you the question
- Reads pseudo-polynomial as 'almost polynomial time'.
- Treats the label as a statement about the problem's difficulty.
- Accepts a fixed word-width cap as the polynomial bound.
- Assumes small magnitudes today guarantee small magnitudes later.
- Thinks the verdict depends only on the code, not on the instances.