Lower Bounds & Adversary Arguments

reduction as a lower-bound tool

Suppose you already know problem A is hard — it provably needs a lot of work. You face a new problem B and suspect it is hard too, but proving a fresh lower bound from scratch is painful. Reduction lets you borrow: if you can solve A quickly whenever you can solve B quickly, then B must be at least as hard as A, so A's lower bound carries over to B. It is the lazy-but-rigorous way to prove hardness — you inherit it instead of reinventing it.

Here is the careful logic, and the direction matters. To prove B is at least as hard as A, you build an algorithm for A that calls B as a subroutine: take any instance of A, cheaply transform it into an instance of B, run the (hypothetical) fast B-solver, then cheaply convert B's answer back into A's answer. If the transformation and conversion are fast (say, O(n)), then a fast B-solver would give a fast A-solver. But we KNOW A has a lower bound, say Omega(n log n). So B cannot be solved faster than Omega(n log n) either, otherwise A could be too, contradicting A's bound. Symbolically: a cheap reduction from A to B transfers A's lower bound to B (minus the cheap glue work). The classic example: the element-distinctness problem reduces to sorting (sort, then scan neighbours for a duplicate), and element distinctness has an Omega(n log n) lower bound in the algebraic model, which is one way to argue sorting-like tasks are hard.

Two honest cautions about direction and what is transferred. Reductions are directional: a reduction FROM A TO B shows B is at least as hard as A, NOT that A is as hard as B, and not that either one is easy. Beginners constantly reduce the wrong way and 'prove' nothing. Also, the glue must be genuinely cheaper than the bound you want to transfer; if transforming the input already costs n log n, you cannot use it to prove an n log n lower bound, because the transformation itself, not B, might be doing the hard work. Reductions are the same tool used for NP-hardness, but here we use them quantitatively, to move concrete time lower bounds like Omega(n log n) between problems within a model.

Element distinctness reduces to closest-pair on a line: if two points coincide, the closest pair has distance 0. So a fast closest-pair solver would detect duplicates fast. Since element distinctness needs Omega(n log n) in the algebraic decision-tree model, closest-pair (even in 1D) inherits the Omega(n log n) floor.

Cheaply turn A into B and back; a fast B then gives a fast A, so A's lower bound binds B.

Direction is everything: reducing A to B shows B is at least as hard as A, not the reverse, and not that either is easy. And the conversion glue must cost less than the bound you transfer, or the glue (not B) is doing the hard work.

Also called
lower bound by reductiontransferring hardness用歸約證下界硬度轉移