Composition of Polynomial Reductions

Prove transitivity while accounting for output length.

Problem

Suppose $A\le_m^p B$ via $f$ and $B\le_m^p C$ via $g$. Prove $A\le_m^p C$. Your runtime argument must account for the length of $f(x)$.

Hint 1

Which function naturally maps an $A$-instance directly to a $C$-instance?

Hint 2

If $f$ runs in time $p(n)$, its output cannot contain more than $p(n)$ symbols. Apply the runtime polynomial for $g$ to that bound.

Full solution

Define $h(x)=g(f(x))$. Correctness is

Let $f$ run in time $p(n)$ and let $g$ run in time $q(m)$ on inputs of length $m$, for polynomials $p,q$. Since a machine can write at most one constant-size symbol per step, $|f(x)|\le p(|x|)$ up to a model-dependent constant. Thus

which is polynomial. Therefore $h$ is a polynomial-time many-one reduction.

Checkpoint

The key step is not merely that two polynomial algorithms are called; the intermediate instance must itself have polynomial length.

Provenance note

This is an original formulation of the standard transitivity proof, aligned with textbook definitions. No student submission is used as authority.

Common mistakes

• Skipping a direction of correctness or an input-format edge case.
• Measuring resources against a numeric value rather than encoded input length.
• Treating an informal intuition as a proof of the stated bound.

Sources and verification

• Merged summary, pp. 43-49
• 2026 transcript 9
• Sipser 3e, sec. 7.4
• Catalog mapping: data/exercises.json; statements and solutions are independently written; personal submissions are non-authoritative.

Open in the visualization gallery: NP-complete reduction chain