Reducibility

Theory of Computation & Computer Graphics — Turing Machine, NEC licence examination syllabus (Nepal Engineering Council).

Reducibility: solving a new problem by disguising it as an old one

The single most useful trick in all of complexity theory — and it's disarmingly simple.

Problem A is reducible to problem B if you can transform any instance of A into an instance of B (in polynomial time), such that solving B also solves A. This means: if B is easy, A is at most as hard as B — and conversely, if A is known to be HARD, that hardness "transfers" to B too.

This is exactly how NP-Completeness proofs work: to prove a NEW problem is NP-Complete, you reduce an ALREADY-KNOWN NP-Complete problem to it — inheriting its hardness, rather than proving hardness from scratch every single time.

💡 One-liner: "If problem A reduces to problem B, and B is solvable in polynomial time, what can you conclude about A?" → A is also solvable in polynomial time — you can solve A by transforming it into B, then solving B.

The direction, which is where the marks are lost

The rule is stated correctly above, but its usefulness depends entirely on getting the direction right — and reversing it inverts the conclusion completely.

➡️ A reduces to B: what follows

If B is easythen A is easy. Solve A by converting it to B and solving that.

If A is hardthen B is hard. If B had an easy solution, A would inherit it — so B cannot be easier than A.

If A is easynothing follows about B. B may be far harder.

If B is hardnothing follows about A. A may be much easier.

So to prove a new problem is NP-hard, reduce a known NP-hard problem to it — known ≤ new. Reducing the new problem to a known one proves only that your problem is no harder than something already difficult, which establishes nothing about its hardness. This reversal is the commonest error in exam answers on reducibility.

💡 A memory aid that holds up: hardness flows forward along the arrow and easiness flows backward. A ≤ B means A is at most as hard as B — so B's easiness helps A, and A's hardness constrains B.

Why the transformation must be efficient

The requirement that the conversion run in polynomial time is not a technicality. Without it the whole argument collapses.

If converting A into B took exponential time, then "solve A by converting to B" would be exponential regardless of how fast B is — so B being easy would tell you nothing about A. The transformation must be cheap relative to the problems, or it hides the very cost being measured.

💡 This is also why reduction is used to prove undecidability, not just hardness. If A is undecidable and A reduces to B, then B must be undecidable too — otherwise deciding B would give a decision procedure for A, which cannot exist. Same argument, applied to a stronger claim.

Syllabus points

Reduction between problems

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.