--- title: "Reductions: Solving One Problem by Turning It into Another" description: "A reduction converts inputs of one problem into inputs of another while preserving their answers. Polynomial-time reductions support algorithm reuse and conditional hardness arguments. The conversion," canonical: https://lightmysky.com/learn/computing/reductions-solving-one-problem-by-turning-it-into-another-mt_PAwby3ZyAr source: https://lightmysky.com/learn/computing/reductions-solving-one-problem-by-turning-it-into-another-mt_PAwby3ZyAr.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # Reductions: Solving One Problem by Turning It into Another A reduction converts inputs of one problem into inputs of another while preserving their answers. Polynomial-time reductions support algorithm reuse and conditional hardness arguments. The conversion, target solver and any solution recovery all contribute to the total cost. Subject: Computing · Area: Algorithms & Data Structures · Ages 21 to 22 Page: https://lightmysky.com/learn/computing/reductions-solving-one-problem-by-turning-it-into-another-mt_PAwby3ZyAr ## Ready when they can - Reduce bipartite matching to maximum flow and state what the conversion costs - Explain why a polynomial-time conversion is needed to transfer a polynomial-time solving guarantee - Use the reduction direction to justify algorithm reuse or a conditional hardness argument ## Lesson: Turn your problem into a solved one You have already turned matching into a flow problem. A reduction from decision problem A to decision problem B converts each input while preserving its yes-or-no answer. Solve the converted input to answer A. For a problem asking for an actual solution, you also need a way to recover that solution from B's output. **Example.** For bipartite matching with V vertices and E edges, add a source and sink. Use capacity 1 on source-to-worker, worker-to-job and job-to-sink edges. The network has V + 2 vertices and E + V edges. Building adjacency lists takes O(V + E) time. Use an integral maximum flow: conservation and unit capacities allow at most one selected edge per worker or job. Scan the E middle edges to recover the matching in O(E) time. *(drawing: Construction and matching recovery are separate parts of the method.)* Polynomial time means a bound by a fixed power of input length. Count conversion, solving and recovery. A polynomial conversion writes at most polynomially many symbols. If conversion takes n^3 steps, writes at most n^2 symbols, and the target solver takes at most m^2 steps on length m, their combined cost is at most n^3 + n^4. An exponential conversion gives no polynomial guarantee. A tightest bound is the smallest growth order justified by the stated algorithm. Suppose A reduces to B in polynomial time. A polynomial-time solver for B gives one for A. Conversely, if A has no polynomial-time algorithm, B cannot have one: such a B solver would produce an A solver. This is a conditional argument. The reduction alone does not establish that a particular source lacks a polynomial algorithm. Check which problem becomes the solver's input. An easy source reducing to a target does not prove the target easy. A source reducing to a target with no polynomial algorithm does not prove the source lacks one. To transfer that lower-bound claim to a new target, the source must already have the lower bound and reduce to the target in polynomial time. **Recap.** A polynomial reduction from A to B lets B's polynomial solver solve A. If A has no polynomial solver, neither does B. Count construction and recovery costs. *Original lesson, questions and flashcards written for this learning dataset.* ## Practice 8 questions on this page, each with its working shown. ## Needs first - [Network Flow and the Max-Flow Min-Cut Theorem](https://lightmysky.com/learn/computing/network-flow-and-the-max-flow-min-cut-theorem-mt_momRV9lK1n) ## Optional connections - [The Halting Problem: A Task No Program Can Do](https://lightmysky.com/learn/computing/the-halting-problem-a-task-no-program-can-do-mt_KeuKGHFWqr) ## Opens up - [Complexity Beyond NP: Space, Randomness and the Hierarchy](https://lightmysky.com/learn/computing/complexity-beyond-np-space-randomness-and-the-hierarchy-mt_ADfgl9UGpO) - [Cryptographic Security Definitions and Proof by Reduction](https://lightmysky.com/learn/computing/cryptographic-security-definitions-and-proof-by-reduction-mt_qPCwxkqYY2) - [P, NP and What NP-Complete Means](https://lightmysky.com/learn/computing/p-np-and-what-np-complete-means-mt_wwmNVG_VnB)