Fine-grained reduction

Let ${\displaystyle A}$ and ${\displaystyle B}$ be computational problems, specified as the desired output for each possible input. Let ${\displaystyle a}$ and ${\displaystyle b}$ both be time-constructible functions that take an integer argument ${\displaystyle n}$ and produce an integer result. Usually, ${\displaystyle a}$ and ${\displaystyle b}$ are the time bounds for known or naive algorithms for the two problems, and often they are monomials such as ${\displaystyle n^{2}}$.[1]

Then ${\displaystyle A}$ is said to be ${\displaystyle (a,b)}$-reducible to ${\displaystyle B}$ if, for every real number ${\displaystyle \epsilon >0}$, there exists a real number ${\displaystyle \delta >0}$ and an algorithm that solves instances of problem ${\displaystyle A}$ by transforming it into a sequence of instances of problem ${\displaystyle B}$, taking time ${\displaystyle O{\bigl (}a(n)^{1-\delta }{\bigr )}}$ for the transformation on instances of size ${\displaystyle n}$, and producing a sequence of instances whose sizes ${\displaystyle n_{i}}$ are bounded by ${\displaystyle \sum _{i}b(n_{i})^{1-\epsilon }<a(n)^{1-\delta }}$.[1]

An ${\displaystyle (a,b)}$-reduction is given by the mapping from ${\displaystyle \epsilon }$ to the pair of an algorithm and ${\displaystyle \delta }$.[1]

Suppose ${\displaystyle A}$ is ${\displaystyle (a,b)}$-reducible to ${\displaystyle B}$, and there exists ${\displaystyle \epsilon >0}$ such that ${\displaystyle B}$ can be solved in time ${\displaystyle O{\bigl (}b(n)^{1-\epsilon }{\bigr )}}$. Then, with these assumptions, there also exists ${\displaystyle \delta >0}$ such that ${\displaystyle A}$ can be solved in time ${\displaystyle O{\bigl (}a(n)^{1-\delta }{\bigr )}}$. Namely, let ${\displaystyle \delta }$ be the value given by the ${\displaystyle (a,b)}$-reduction, and solve ${\displaystyle A}$ by applying the transformation of the reduction and using the fast algorithm for ${\displaystyle B}$ for each resulting subproblem.[1]

Equivalently, if ${\displaystyle A}$ cannot be solved in time significantly faster than ${\displaystyle a(n)}$, then ${\displaystyle B}$ cannot be solved in time significantly faster than ${\displaystyle b(n)}$.[1]

Fine-grained reductions were defined, in the special case that ${\displaystyle a}$ and ${\displaystyle b}$ are equal monomials, by Virginia Vassilevska Williams and Ryan Williams in 2010. They also showed the existence of ${\displaystyle (n^{3},n^{3})}$-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.[3]