In computational complexity theory, a fine-grained reduction is a transformation from one computational problem to another, used to relate the difficulty of improving the time bounds for the two problems.
Intuitively, it provides a method for solving one problem efficiently by using the solution to the other problem as a subroutine.
can be solved in time
can be solved in time
implies that any significant speedup for problem
would also lead to a speedup for problem
be computational problems, specified as the desired output for each possible input.
both be time-constructible functions that take an integer argument
and produce an integer result.
are the time bounds for known or naive algorithms for the two problems, and often they are monomials such as
if, for every real number
, there exists a real number
and an algorithm that solves instances of problem
by transforming it into a sequence of instances of problem
, taking time
for the transformation on instances of size
, and producing a sequence of instances whose sizes
to the pair of an algorithm and
can be solved in time
can be solved in time
by applying the transformation of the reduction and using the fast algorithm for
for each resulting subproblem.
cannot be solved in time significantly faster than
cannot be solved in time significantly faster than
[1] Fine-grained reductions were defined, in the special case that
are equal monomials, by Virginia Vassilevska Williams and Ryan Williams in 2010.
-reductions between several problems including all-pairs shortest paths, finding the second-shortest path between two given vertices in a weighted graph, finding negative-weight triangles in weighted graphs, and testing whether a given distance matrix describes a metric space.
According to their results, either all of these problems have time bounds with exponents less than three, or none of them do.
[2] The term "fine-grained reduction" comes from later work by Virginia Vassilevska Williams in an invited presentation at the 10th International Symposium on Parameterized and Exact Computation.
[1] Although the original definition of fine-grained reductions involved deterministic algorithms, the corresponding concepts for randomized algorithms and nondeterministic algorithms have also been considered.