---
title: "Reductions: Solving One Problem by Turning It into Another"
description: "A reduction converts every instance of one problem into an instance of another, so a solver for the second answers the first. Read forwards it reuses an algorithm, and read backwards it transfers hard"
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-09-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 every instance of one problem into an instance of another, so a solver for the second answers the first. Read forwards it reuses an algorithm, and read backwards it transfers hardness from a problem nobody can solve quickly.

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 reduction has to run quickly for the argument to mean anything
- Say which direction of a reduction proves easiness and which proves hardness

## Lesson: Turn your problem into a solved one

You already know flow finds a maximum through a network. A reduction converts every instance of one problem into an instance of another. Then a solver for the second problem answers the first one for free.

**Example.** To match workers to jobs, build a flow network with a source, a sink, and unit capacities, then run max flow. The conversion costs almost nothing beside building the small network, and the matching reads straight off the used edges.

Read forwards, a reduction reuses an algorithm: if the target is easy, your problem is easy too. Read backwards, it transfers hardness: if your problem is hard, the target must be hard as well. Easiness flows one way, hardness the other.

**Tip.** Two checks before you claim anything. The conversion itself must run quickly, or the argument means nothing. And the direction must match the claim: the wrong way round proves nothing about the problem you care about.

**Recap.** Convert cheaply to a solved problem, reuse its solver forwards, and transfer hardness only backwards.

## Practice

8 questions on this page, each with its working shown.

## Needs first

- [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)
- [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)

## 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)