skip to content

In a reduction assembled from local gadgets, what must each gadget forbid for the construction to be valid?

level: seniorimportance: nice to knowfreq 28%

answer

  1. small fixed fragments, then wiring
  2. two obligations, not one
  3. cheating configurations are the enemy
  4. every target solution must decode back
  5. polynomial of a polynomial

basics

~10 s

Each gadget must forbid configurations that solve the target instance without corresponding to anything in the source. Such a cheating configuration turns a no-instance into a yes and destroys the equivalence.

solid answer

~40 s

Most hardness reductions are built by replacing each piece of the source instance — a variable, a clause, a constraint — with a small fixed fragment of the target instance, then wiring the fragments together. Each gadget carries two obligations. **Completeness**: any solution of the source instance can be assembled into a solution of the target one. **Soundness**: every solution of the target instance restricts back to a solution of the source. Soundness is the half gadgets break, because a fragment often admits some local configuration that satisfies the target's rules while meaning nothing in the source. That single loophole lets a no-instance map to a yes-instance, and the whole argument collapses. Gadgets also stay small and are assembled in polynomial time, which is what keeps the map cheap.

code

pseudocode · 7 lines
pseudocode
function compose(x):           // x is an instance of A
    y = f(x)                   // A -> B, runs in time p(size(x))
                               // so size(y) <= p(size(x)): output is
                               // bounded by the time spent writing it
    z = g(y)                   // B -> C, runs in time q(size(y))
    return z                   // total <= p(size(x)) + q(p(size(x)))
                               // a polynomial of a polynomial

go deeper

for a junior

Know the vocabulary: a gadget is a small reusable fragment that stands for one piece of the original problem, and the fragments are wired together to form the translated instance.

for a middle

Explain the two obligations in your own words and say which one a permissive fragment breaks, and what that does to the equivalence the reduction claims.

for a senior

Demonstrate the checking discipline: enumerate a gadget's configurations, label each with its source meaning, and push a known no-instance through the whole assembly by hand.

for a principal

Treat source choice as a risk decision. A structurally near source means fewer gadget families, fewer configurations to defend, and a shorter argument for others to review.

## What a gadget is A **gadget** is a small, fixed fragment of the target problem's instance that stands in for one piece of the source instance. Replace each source piece with its gadget, connect the gadgets according to how the source pieces relate, and the assembled object is `f(x)` — the target instance the reduction produces. The whole construction is local: each fragment is built independently, in constant or near-constant work, which is what keeps the total polynomial. The design question is never "does this fragment look like that source piece". It is: **which configurations does this fragment allow?** ## The two obligations, and which one breaks 1. **Completeness (the yes-direction).** If the source instance has a solution, the gadgets can be set consistently so that the target instance has one. This is usually the easy half: you built the gadget from the source piece, so you know how to fill it in. 2. **Soundness (the no-direction).** Every solution of the target instance can be read back as a solution of the source. Equivalently: the gadget admits *no* configuration whose meaning in the source is undefined or contradictory. Soundness is where constructions die. A fragment that is one constraint too permissive will have a stray satisfying configuration — a "cheating" setting — and an engine or an adversarial argument will find it. Then a source no-instance maps to a target yes-instance, the equivalence is only an implication, and every conclusion drawn from the reduction is void. | Failure | What it means | Symptom when you test it | |---|---|---| | Completeness fails | a source solution has no assembled counterpart | a known yes-instance maps to an unsolvable instance | | Soundness fails | a target solution decodes to nothing valid | a known no-instance maps to a solvable instance | ## Checking a gadget honestly - **Enumerate the gadget's local configurations** — there are usually few — and label each with the source meaning it encodes. Any configuration left unlabelled is a soundness hole. - **Push a known no-instance through by hand** and satisfy yourself the assembled instance really has no solution. - **Check the wiring, not only the fragments.** Gadgets that are individually sound can leak at the joins, where a shared element lets two fragments disagree about what it encodes. - **Confirm the gadget is size-bounded** independently of the source instance, so the assembly stays polynomial. ## Why chaining reductions is legitimate Reductions compose: if `A <=p B` and `B <=p C`, then `A <=p C`. Two facts make this work, and the second is the one usually left unsaid. 1. The answer equivalences chain. A yes-instance of `A` becomes a yes-instance of `B`, which becomes a yes-instance of `C`, and the same walk runs for no-instances and in reverse. 2. The **cost** stays polynomial. A polynomial-time function cannot write more than a polynomial amount of output, so the intermediate instance is polynomially bounded in the original input. The second map, polynomial in *its* input, is therefore polynomial in the original size, and a polynomial of a polynomial is a polynomial. That second point is why composition would fail for a map allowed to produce exponentially large intermediate output even if it somehow ran quickly: the second stage would then be polynomial in something exponential, which is not polynomial in the original. ## Why this matters in practice Composition is what makes a catalogue of hard problems useful: once a problem is established as hard, you may reduce *from it* rather than from first principles, and the chain back to the original result is still valid. It also means you should pick the source problem that is structurally nearest to yours, because each link you avoid is a gadget family you do not have to design, check for soundness and defend. A reduction from a distant source is not more impressive; it is more surface area for a cheating configuration to hide in.

  • Why does a polynomial map's output size never need a separate assumption?
    Because a machine cannot write more symbols than the steps it takes. A map running in polynomial time therefore produces output of polynomially bounded size, which is exactly what lets a second polynomial map run on it and still be polynomial in the original input.
  • Two gadgets are individually sound. Can the assembled instance still be unsound?
    Yes. Soundness holes commonly live at the joins, where fragments share an element and nothing forces them to agree on what it encodes. Check the wiring as a construction in its own right, and decode a full target solution end to end rather than gadget by gadget.
  • Does choosing a structurally closer source problem make a hardness argument weaker?
    No. Any established hard source gives the same conclusion, and composition keeps the chain back to the original result valid. A nearer source means simpler gadgets, fewer configurations to enumerate and less room for a soundness hole, so it is the better engineering choice.

saying these in an interview costs you the question

  • Checks only that source solutions survive the construction
  • Never enumerates the configurations a gadget allows
  • Assumes sound fragments compose into a sound instance
  • Lets gadget size grow with the whole source instance
  • Thinks chained reductions need a fresh proof each time
  • Treats a distant source problem as a stronger result