JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Lower Bounds by Reduction

The previous guides earned lower bounds the hard way — by reasoning about decision trees and arguing with an adversary. Reduction is the lazy genius's shortcut: prove one bound, then transport it to a whole family of problems by showing they can secretly solve the first.

Where this rung has carried us

You have now met three ways to prove that a problem cannot be solved faster than some threshold — that no algorithm, however clever, beats it. The first guide pinned down what a lower bound even claims: a statement about every possible algorithm in a model, not about one program. The decision-tree model gave that claim a shape: any comparison-based method is a tree of yes/no questions, and a tree with L reachable leaves needs depth at least log2(L). From there the Omega(n log n) bound for comparison sorting fell out almost for free, because sorting must distinguish all n! orderings, and log2(n!) is Theta(n log n). Then the adversary argument gave a second, hands-on technique: an opponent who answers your queries to keep as many outcomes alive as possible, forcing you to ask many questions.

Both of those are direct attacks: you stare at the problem itself and count what it must do. This final guide gives you a fourth tool that is utterly different in spirit and often far easier to wield — reduction. The idea is to borrow a lower bound you already trust. If solving problem B quickly would let you solve problem A quickly, and you already know A is hard, then B must be hard too — otherwise you would have a fast A by going through B. You never reason about B's internal difficulty at all. You just plumb it to a problem whose hardness is already settled. That borrowing is what makes reduction the workhorse of hardness results across all of algorithms and complexity.

The shape of a lower-bound reduction

Let us make the logic airtight, because reductions are famous for getting flipped by accident. A reduction from A to B is a recipe that turns any instance of A into an instance of B, runs a (hypothetical) solver for B, then translates B's answer back into an answer for A. If both the translation steps are cheap relative to the bound we are chasing, then any solver for B gives us a solver for A of essentially the same speed. Read that sentence twice: a reduction from A to B shows that B is at least as hard as A, not the other way around. We push the hard problem A through B to prove B inherits A's difficulty. Beginners constantly reverse this; keep the arrow pointing from the known-hard problem into the problem you want to indict.

  1. Start with a known-hard problem A, whose lower bound you already trust (here, sorting at Omega(n log n)).
  2. Map an arbitrary instance of A into an instance of B, using only cheap work — at most O(n) here.
  3. Imagine a fast solver for B runs on that instance and returns its answer.
  4. Translate B's output back into the answer A demanded, again cheaply (at most O(n)).
  5. Conclude: a fast B would yield a fast A; since A is impossible to speed past its bound, B inherits that bound.

The classic: element distinctness is sorting in disguise

Here is the cleanest reduction in the subject. Element distinctness asks: given n numbers, are they all different, or is some value repeated? It feels easier than sorting — we only want a yes/no, not a full arrangement. Yet in the comparison model it costs Omega(n log n) too, and reduction proves it in a sentence. Suppose someone hands you a magic box that decides distinctness in o(n log n) comparisons. We will use it to sort, which is impossible below n log n, so the box cannot exist.

But wait — a distinctness box outputs only "yes" or "no"; how could that ever sort? This is the subtle and beautiful part, and it is why element distinctness is the textbook example. The reduction does not go through the comparison-sorting problem directly. It goes through a geometric cousin whose lower bound is itself proved by an algebraic-decision-tree argument: the number of connected components of the "all-distinct" region in n-dimensional space is n!, and an algebraic decision tree separating that many components needs depth Omega(n log n). The honest takeaway for this guide is the form of the argument — a cheap wrapper plus a borrowed bound — even though the borrowed bound here comes from the algebraic-decision-tree model rather than from sorting itself. Many texts state the chain loosely as "distinctness is as hard as sorting"; the precise version routes the n! through geometry.

Carrying the bound onward: convex hull and friends

Once you own one n log n bound, reduction lets you franchise it across geometry. Consider the convex hull: given n points in the plane, find the smallest convex polygon containing them all, with its vertices listed in order around the boundary. The convex-hull lower bound is Omega(n log n), and the reduction from sorting is delightfully visual. Take n numbers x_1, ..., x_n you wish to sort. Lift each onto the parabola y = x^2, producing the point (x_i, x_i^2). Every such point is a vertex of the convex hull because the parabola is convex — no point lies inside the others. So a hull algorithm must return all n points, and it returns them in order around the boundary, which along the bottom of the parabola is exactly sorted order. Read off the x-coordinates and you have sorted the numbers.

to sort  x_1 .. x_n :
    map each x_i  ->  point ( x_i , x_i^2 )    # O(n), lift onto parabola
    H = ConvexHull( points )                   # all n points are hull vertices
    read x-coords of H in boundary order       # O(n), this is sorted order
# a sub-(n log n) hull  =>  sub-(n log n) sort  =>  impossible
The sorting-to-convex-hull reduction: a linear wrapper on each side forces the hull bound up to Omega(n log n).

Both wrapping steps — the lift onto the parabola and the reading-off — are clearly O(n). So a convex-hull algorithm running in o(n log n) would yield an o(n log n) sort, which we proved impossible. Therefore the hull needs Omega(n log n), and the bound is tight: the Graham scan and other algorithms achieve O(n log n), so we have matched the floor to a real ceiling. The same parabola trick, or close relatives, transfers the n log n bound to the closest pair of points and to computing the intersection of half-planes — a whole neighbourhood of computational geometry inherits its hardness from sorting through one-line reductions.

Why reduction is the bridge to the rest of complexity

Everything above used reductions to move an exact Omega(n log n) bound between concrete problems in a comparison-style model. But the very same logical move, scaled up, is the engine of the most famous hardness theory there is. A polynomial-time reduction from A to B says: convert any A-instance to a B-instance in polynomial time, so that a polynomial-time B-solver gives a polynomial-time A-solver. That is identical in spirit to our parabola trick — only now "cheap" means "polynomial" instead of "linear", and "hard" means "no known polynomial algorithm" instead of "below n log n". This is how a single seed of hardness spreads to thousands of problems at once.

Here, though, lives the deepest honesty of the whole subject. The n log n bounds we proved are unconditional — they hold absolutely within their model, no assumptions attached, because the decision-tree counting is airtight. The polynomial-time hardness results are conditional. When we call a problem NP-hard by reduction, we have shown it is at least as hard as every problem in NP, but we have not proven it needs exponential time. Whether any of them does is the open P versus NP question — the most famous unsolved problem in computer science. "NP-complete" means no polynomial algorithm is known and one for any single such problem would give one for all of them, not that none can exist. The reduction is rock-solid; what it rests on for NP-hardness is a conjecture, and saying otherwise would be a lie.

Step back and feel the unity of this rung. A lower bound says "no algorithm can do better"; we earned a few directly by counting decision-tree leaves and by playing adversary, and we earned many more cheaply by reduction — borrowing a proven floor and carrying it, on a thin linear wrapper, into element distinctness, convex hull, closest pair, and beyond. And when you climb past this rung into NP-completeness, the only new ingredient is the scale of "cheap": swap linear wrappers for polynomial ones and the same borrowing turns one hard problem into thousands. Reduction is the idea that lets hardness, once established anywhere, travel everywhere it is needed.