skip to content

What must a polynomial-time many-one reduction from problem A to problem B guarantee about every instance it maps?

level: middleimportance: must knowfreq 62%

answer

  1. one instance in, one instance out
  2. the answer must survive the trip
  3. no-instances matter as much as yes
  4. the translator must stay cheap
  5. if and only if, both directions

basics

~10 s

A polynomial-time many-one reduction turns any instance of A into one instance of B using only polynomial work, and guarantees the answer survives the trip: yes maps to yes, and no maps to no.

solid answer

~50 s

It is a function `f` you can compute in time polynomial in the input size, taking one instance `x` of problem A to one instance `f(x)` of problem B, such that `x` is a yes-instance of A **exactly when** `f(x)` is a yes-instance of B. Both halves of that equivalence are obligations: preserving yes-instances is easy and worthless on its own, because a map that sends everything to a fixed yes-instance would qualify. The no-direction is what forbids the encoding from inventing solutions that the original problem does not allow. The map is also all you get — it hands back an instance, not an answer and not a solution — so the reduction itself never solves anything. And the cost matters: if the translation were allowed to be expensive, it could do the real work in secret and the relationship it claims would carry no information.

code

pseudocode · 7 lines
pseudocode
function decide_A(x):
    y = translate(x)          // polynomial work in size(x)
    verdict = engine_for_B(y) // the only thing that decides anything
    return verdict            // yes/no comes back unchanged

// obligation on translate:
//   answer_A(x) = yes  <=>  answer_B(translate(x)) = yes

go deeper

for a junior

Remember the shape: a reduction is a translation between problems, not a solver. It rewrites one question as another question and leaves the answering to something else.

for a middle

Be able to state the definition precisely: a polynomial-time function on instances with a two-way equivalence between yes-instances. Explain why the no-direction is the half that does the work.

for a senior

Show you check the no-direction on a concrete instance and that you know the map returns an instance, not a schedule or a solution, so any usable pipeline needs a decoding step you wrote yourself.

for a principal

Frame the polynomial bound as the line between a translation that transfers structure and one that hides the computation inside itself, and be ready to say why polynomially bounded growth is still an engineering cost.

## The object itself A **many-one reduction** (also called a *mapping* reduction, or a *Karp* reduction when the bound is polynomial) from problem `A` to problem `B` is not an argument, a proof sketch or an analogy. It is a **function**, and it has exactly three properties you must be able to state: 1. **Total**: it accepts *every* instance `x` of `A` and produces *one* instance `f(x)` of `B`. Not a set of instances, not a sequence of queries — one. 2. **Answer-preserving in both directions**: `x` is a yes-instance of `A` **if and only if** `f(x)` is a yes-instance of `B`. 3. **Cheap**: `f` is computable in time polynomial in the size of `x`. Write it as `A <=p B` and read it aloud as "A reduces to B in polynomial time", which is also read as "B is at least as hard as A, up to polynomial factors". ## Why the no-direction is the real content The yes-direction alone is free. A map that ignores its input and emits one fixed yes-instance of `B` preserves every yes-instance of `A` perfectly, and it is obviously worthless. What rules that map out is the other half of the equivalence: if `x` is a **no**-instance of `A`, then `f(x)` must be a **no**-instance of `B`. That is where real reductions break. The translation is usually assembled from small fragments, and a fragment that permits one configuration with no counterpart in the original instance turns some no-instances into yes-instances. The equivalence is then only an implication, and every conclusion drawn from it is unsound. In practice this is the bug you hunt for when a reduction "almost" works. ## Why the map must be cheap Suppose the translation were allowed to run for exponential time. Then it could simply decide `A` itself and emit a trivial yes-instance or a trivial no-instance of `B` accordingly. The equivalence would hold perfectly and the reduction would say nothing whatsoever about `B`, because all the work happened inside `f`. The polynomial bound is what forces the *structure* of `A` to be carried into `B` rather than consumed by the translator. A useful corollary: a polynomial-time function cannot write more than a polynomial amount of output, so `|f(x)|` is automatically polynomially bounded in `|x|`. That fact is what makes reductions compose. ## What the equivalence lets you conclude | You have | Plus | You may conclude | |---|---|---| | `A <=p B` | a polynomial-time algorithm for `B` | `A` has one too: translate, then run it | | `A <=p B` | `A` is known to be hard | `B` is at least as hard as `A` | | `A <=p B` | nothing else | nothing about `A` being hard | The third row is the one candidates skip. Producing a map *out of* your problem is evidence about an **upper** bound on your problem's difficulty, never a lower one. ## What a reduction does not give you - **It does not return an answer.** It returns an instance. You still need something that decides `B`. - **It does not promise a solution you can use.** The definition preserves the yes/no bit only. Most constructions are concrete enough that a solution of `f(x)` can be read back as a solution of `x`, but that back-map is extra work you write and justify yourself. - **It does not promise a small instance.** Polynomial bounds growth; it does not make it modest. Squaring a large instance is polynomial and can still be fatal in practice. - **It does not care which problem is "more natural".** Direction is fixed by the equivalence, not by intuition about which problem feels harder. ## How to say it in an interview State the signature first — a function from instances to instances — then the `if and only if`, then the polynomial bound, and only then what you would *use* it for. Candidates who begin with "you show your problem is basically the same as" almost always end up with a claim they cannot defend, because "basically the same" hides which way the equivalence was actually proved and whether the no-instances were checked at all. A final sanity habit: after writing any reduction, take one concrete no-instance of the source, push it through the map by hand, and satisfy yourself that the resulting target instance genuinely has no solution. That single exercise catches most broken constructions before anyone else reads them.

  • What goes wrong if the map sends some no-instance of A to a yes-instance of B?
    The equivalence collapses to a one-way implication. A wrapper built on it now reports yes where the real answer is no, so it is simply an incorrect algorithm, and no hardness conclusion can be drawn from the map either. A spurious yes is the classic construction bug.
  • Why must the translation itself run in polynomial time?
    Because an expensive translator could decide the source problem itself and emit a canned yes- or no-instance. The equivalence would hold while telling you nothing about the target problem. The polynomial bound forces the structure of the source instance to be carried across rather than consumed.
  • Does a many-one reduction hand you an actual solution, or only a verdict?
    By definition, only the verdict: it preserves the yes/no bit. Most concrete constructions are built so that a solution of the target instance can be decoded back into one for the source, but that decoding is additional work you must write and argue for; it is not part of the definition.

Think of a sworn translator who rewrites a question into another language so faithfully that a yes over there means yes over here, and a no means no. The translator never answers the question — someone else does that, in the other language.

saying these in an interview costs you the question

  • Thinks preserving yes-instances alone is enough
  • Lets the translation call a solver for the source problem
  • Expects the reduction to return a solution rather than an instance
  • Allows exponential blow-up as long as the map terminates
  • Calls any informal 'these problems are similar' argument a reduction
  • Assumes a polynomial map produces a comparably sized instance