“因此，在固定多项式权界及相同精确计算模型下，一个任务有固定指数节省的真次三次算法，当且仅当另一个也有。这是细粒度等价：对数开销可用稍小的固定指数余量吸收，不是这里已经证明了两个时间函数逐常数…”
形式陈述
先指定要保存哪一种速度
多项式归约可以花n的十次方时间；若原问题已有三次算法，这样的翻译不能解释二点九次算法是否可能。细粒度归约因此将问题和基准时间一起比较，而不是只比较两个问题名。
固定计算模型、输入编码与规模参数，设问题A、B的基准时间为a(n)、b(n)，均至少为1。问题可以要求一个判定位，也可以要求唯一确定的完整函数值。规模可以是编码长度，也可以是明示的顶点数；后二者不相等，读入和输出成本仍须收费。以下先定义确定性、精确回答的版本。[1, §2.2]
写作(A,a)≤FG(B,b)，是指：对每个0<ε<1，存在δ>0和一份归约Rε，在每个规模n的合法A输入上正确求解A，并满足：
- 除求解器内部工作外，Rε的运行时间为O(a(n)^(1−δ))。
- 它依次产生B输入x₁,…,xq，规模为n₁,…,nq，并有
Rε是一种Turing式归约：后一个输入可以依赖先前正确答案。外层时间包含构造和写出所有输入、读取答案、合并结果，不把一张大矩阵当一个免费oracle位。常数可依赖固定ε，不能随实际输入变化；两项上界须对全部合法执行成立。
ε是目标相对基准的指数节省。若b(n)=n³，b(n)^(1−ε)是n^(3−3ε)，不是n^(3−ε)。文献也常直接使用后者的绝对节省记法，换算即可，不能在同一预算里悄悄换字义。
它直接给出什么结论
若B有O(b(n)^(1−ε))时间精确算法，就用它替换每次调用。外层工作与全部调用分别受同一个a(n)^(1−δ)控制，故A也有这个时间上界。困难性是该事实的逆否命题：若A不存在这类固定指数改进，B也不可能存在被归约承接的改进。
定义本身没有证明A困难。即使某个旧假设被更快算法推翻，归约仍然正确，还会将目标的新算法传回源问题。APSP与距离积的等价展示这种不依赖困难性假设的算法关系。
直觉
把目标求解器想成一台可租用的机器。机器每次服务变快，不代表整个流程一定变快：翻译可能已经太慢，输入可能被放大，还可能反复租用太多次。细粒度归约检查的是这三笔费用相加后，是否仍比源问题的旧基准少一个固定的指数。
“固定”很重要。把n³除以log n确实更快，但对任意固定η>0，n³/log n都不是O(n^(3−η))。取对数后，log log n远小于η log n；因此削去对数不能自动填进固定指数节省的定义。
例子与边界
一份预算可以逐行验算
设源、目标基准分别为n³、m²。一项已证明答案正确的归约，外层耗时O(n²)，发出n个规模n的目标查询。若目标改成O(m^(2−η))，其中0<η≤1，总时间是
在定义的记号里，ε=η/2、δ=η/3。取η=1/2，则n=64时，目标计费单位合计为64×64^(3/2)=32768，源基准64³=262144。这个有限算例用于检查指数换算，渐近结论来自对所有n成立的公式。
现在只改查询规模，把每次输入放大到n²。调用账变成
η=1/2时甚至达到n⁴；目标的一点改进被规模膨胀吞掉。再如，若外层本来就要n³步，哪怕全部查询瞬间返回，也不能由这一归约推出源问题真次三次。这里否定的是这份速度传递论证，不是在证明源问题没有别的快算法。
这些式子只检验成本。还必须另外证明每个目标输入合法、答案怎样恢复、所有分支都正确；凭一张指数表不能发明一道新归约。
多次调用不能只算最大实例
假设q个查询都至多m，q·b(m)^(1−ε)是可用的粗上界；但只写b(m)^(1−ε)会漏掉q。反过来，若查询规模差异很大，逐项求和可能明显小于把所有查询都放大到最大规模。
旧的SAT分半到正交向量已有完整例子：两表规模约2^(n/2)，目标二次指数节省可变成SAT指数底数的固定节省；若先稀疏化成2^(ηn)个分支，还要乘这份分支数。该页保存了答案证明与稀疏化预算，本页提供这些费用共同遵守的接口。
预处理与数据类型仍属于输入
“预处理一次，之后查询很快”必须说明一次针对什么。若表依赖每个新目标实例，它属于每次调用；若能跨调用复用，归约要展示相同的固定输入部分，以及表的实际构建成本。OMv归约会通过小块重组付清这笔费用，而不是直接抹掉预处理。
整数权的位长、实数运算模型、允许的错误率也不会因归约箭头自动保持。把一个整数编码成指数大数，再免费做精确乘法，可能已经更换了计算模型。把近似答案当成精确oracle，同样需要另证舍入是否保持源答案。
推论与应用
归约为什么能复合
设(A,a)≤FG(B,b)，且(B,b)≤FG(C,c)。给定C的目标节省ε，先由第二个归约得到B的节省γ>0；若γ过大可缩小到小于1。再将γ交给第一个归约，得到A的节省δ>0。
对第一个归约产生的第i个B输入，第二个归约的外层工作与其全部C调用费用均为O(b(nᵢ)^(1−γ))。对i求和，正好被第一个归约的查询账本控制。因此复合后的外层工作及全部C查询费用仍为O(a(n)^(1−δ))。
自适应性不妨碍这个论证：第二个归约正确返回每个B答案，第一个归约便沿本来正确的分支继续。关键是时间界对每个合法查询都成立，而不是只对某些平均输入成立。
随机oracle要为整段执行控制错误
确定性归约接一个带错误的求解器，通常得到随机算法，不能据此反驳只谈确定性算法的假设。若要保存总失败概率至多1/3，须再计概率与放大费用。
考虑至多Q(n)次调用、每个固定输入的唯一正确答案以至少2/3概率返回、各次重跑使用独立随机位的情形。每个查询独立重跑O(log(Q+2))次，取完整答案的多数，可将单次错误压到1/(3(Q+1))。输出若是向量，取的是整条向量的多数；读取和比较向量的工作不能省掉。
即使查询自适应产生，也可考察“第一次出错”：在此前所有回答正确的条件下，当前查询已经固定，新的独立随机位仍满足该输入上的失败界。对至多Q次首次错误事件相加，总失败概率至多1/3。
若Q为n的多项式，放大只带来O(log n)因子。对多项式基准，有固定正指数余量时可缩小余量吸收它，例如n^(3−η)log n=O(n^(3−η/2))。没有余量，或者总调用数不受所宣称范围控制时，不能自动套用这句话。
终点检查一条完整箭头
综合练习同时运行两类归约：静态图与矩阵之间的双向转换，以及逐轮到达向量的动态图查询。交付时应写出输入参数、真实调用序列、外层费用、oracle费用和最后输出；有错误的候选必须能指出究竟漏了哪一项。
参考资料
- Virginia Vassilevska Williams，On Some Fine-Grained Questions in Algorithms and Complexity，ICM2018作者稿，§2.2、Definition2.1，PDF p.6：含查询费用求和的细粒度Turing归约。本文将外层读写、指数两种记法和随机放大费用展开。
- Virginia Vassilevska Williams、Ryan Williams，Subcubic Equivalences Between Path, Matrix, and Triangle Problems，FOCS2010的作者扩展稿，§1：整数权位长与真正次三次的归约框架。关于当时算法前沿的叙述属于该稿发表时间，不作为当前状态依据。