Your service translates each request into an instance for a general-purpose engine, so what can still go wrong when the map is polynomial?

## The setting You have a requirement that is awkward to solve directly, and a general-purpose engine for some well-studied target problem. So you write a **translator**: each incoming request becomes one instance of the target problem, the engine decides it, and you report the verdict. This is the `yours <=p solved` direction, used as an implementation strategy rather than as a proof. The theory says the pipeline is correct whenever the map preserves yes and no and runs in polynomial time. Production then finds the gaps the theory was never making claims about. ## Gap one: polynomial is not small Polynomial bounds the *shape* of the growth curve, not the size of any particular instance. A map that produces a constraint per pair of items is quadratic, which is polynomial and entirely respectable, and it turns ten thousand items into a hundred million constraints. The usual closure result — a polynomial map followed by a polynomial algorithm is polynomial — assumes the target has a polynomial-time algorithm. When you are reusing an engine for a target that is believed intractable in general, the engine's cost climbs sharply with instance size, so **growth in the map is multiplied, not absorbed**. Things to measure before committing: - The exponent of the map, in the dimension of the input that actually varies in production. - The engine's observed cost curve on instances your map produces, not on published families. - Whether the map's growth is in a dimension that is capped by the domain, which turns a bad exponent into a constant. ## Gap two: fidelity, and which direction fails The equivalence has two halves, and they fail differently. | Half that breaks | What the pipeline does | How it is noticed | |---|---|---| | yes-instance maps to a no-instance | reports impossible for a request that is satisfiable | quickly — someone knows the request was fine | | no-instance maps to a yes-instance | reports a solution that violates the real requirement | late, and often downstream | The second is the dangerous one. It happens when the encoding is slightly **looser** than reality: a constraint you assumed was implied, a symmetry you forgot to break, a unit or a boundary case the target problem's representation cannot express. The engine is not wrong; it is faithfully solving the instance you handed it. Defences that work: 1. **Differential testing** — run a slow, obviously correct checker over the engine's verdict on real instances. You are testing the *translation*, and the check runs against your domain rules, not against the engine. 2. **Validate the returned assignment in domain terms** before acting on it. A yes you cannot validate is a yes you should not trust. 3. **Keep a corpus of no-instances** — requests that genuinely have no solution — because a broken encoding passes every yes-only test suite. ## Gap three: the verdict is not the deliverable A mapping reduction promises the yes/no bit. Callers rarely want a bit; they want the arrangement. Most constructions are concrete enough that the engine's solution decodes back into your domain, but that decoder is code you own, it can drift out of step with the encoder, and it is the natural place for an off-by-one to live unnoticed. Treat encoder and decoder as one unit with one test suite. Relatedly, if your real requirement is an optimisation — the *best* arrangement rather than *any* — the target's decision form does not answer it directly. You get there by asking about a threshold and moving it, which multiplies the engine calls and changes the cost conversation entirely. ## What good judgment sounds like A senior answer does not stop at "the reduction is polynomial, so we are fine". It names the exponent, says which production dimension it is polynomial *in*, describes how the no-direction is tested, and states what the system does when the engine exceeds its time budget on a real request — because "the engine is still thinking" is a state your callers will see long before any asymptotic claim becomes relevant.