“由此不能继续把“传统APSP假设仍成立”作为未经标注的当前困难性依据。另一方面，既有细粒度归约没有失效：它们也能传递新算法。关于原始在线布尔矩阵向量任务的OMv猜想则有不同信息接口，不能因另…”
形式陈述
一张矩阵，随后n轮输入
先给n×n布尔矩阵M。之后依次给n个布尔列向量v¹,…,vⁿ，每个长度n。第t轮必须输出整个Mvᵗ，才会收到vᵗ⁺¹。这份在线约定限制可见信息，允许保存矩阵和过去全部输入，却不允许先把未来向量组成另一张矩阵。[1, §1]
乘法取布尔半环：
它不是模2内积。一行有两个共同的1仍然输出1，不能因1+1在模2下为0便输出0。
OMv猜想断言：对每个常数ε>0，不存在一个经典随机算法，在O(n^(3−ε))总时间内完成这个任务，并对每个固定合法输入序列以至少2/3概率给出全部n轮正确答案。[1, Conjecture1.1] 使用通常O(log n)字宽的Word-RAM；读取矩阵、矩阵相关预处理、各轮读入和输出都在总时间中。
这里选最坏运行时间及有界错误版本。确定性精确算法是它的特例；只有期望时间的算法需要另外说明截断及失败概率。猜想是条件下界的前提，不是已经证明的无条件下界，更不可能靠有限测试证实。
本页证明的动态后果
考虑固定N点、允许插入和删除边的有向图，固定源点s，查询“s能否到达给定点r”。如果一种结构满足：
- 预处理P(N)=O(N^c)，c为某个固定常数；
- 在任意多项式长度的合法操作序列中，总费用由P(N)+更新数·O(N^(1−ε))+查询数·O(N^(1−ε))控制；
- 答案精确，或对固定序列的错误率可按后文的独立重复控制；
其中ε>0固定，则它会给出真次三次OMv算法。因此在OMv猜想下，三项保证不能同时成立。下面先给直接归约，再证明如何支付任意固定多项式预处理，不把它免费排除。
直觉
矩阵的第j列告诉我们：当前向量在j处为1时，哪些输出行会被激活。用一个顶点代表列，再从它连向所有Mᵢⱼ=1的行顶点。源点只连向当前向量为1的列，于是某行可达，当且仅当至少有一个激活列支持它。
换下一个向量只需改源点出边，矩阵对应的列到行弧一直保留。这个图只有两步路线，没有环；困难不来自复杂路径形状，而来自在许多未知的新向量之间同时保持很快的更新和回答。
普通离线矩阵乘法已经看到了全部列向量。即使它能很快算出M[v¹…vⁿ]，也不能在第二列尚未揭示时替第一轮借用那份完整输入。
例子与边界
源边怎样编码当前向量
建顶点s、列顶点c₀,…,cₙ₋₁、行顶点r₀,…,rₙ₋₁，总数2n+1。每个Mᵢⱼ=1建cⱼ→rᵢ。第t轮令s→cⱼ存在恰当且仅当vᵗⱼ=1。除了这些弧，不再建其他弧。
图中每条从s到rᵢ的路线都必须是s→cⱼ→rᵢ。因此
每轮比较新旧向量，至多n次源边插删，再查询n个行顶点，便得到整个输出。保留旧源边而只添加新的1，会把前轮向量混进本轮，不能正确处理1变0。
取
四轮输入与结果为：
| 轮次 | 当前v | Mv | 与前轮相比的源边修改数 |
|---|---|---|---|
| 0 | 1010 | 1101 | 2 |
| 1 | 0101 | 0101 | 4 |
| 2 | 0000 | 0000 | 2 |
| 3 | 1111 | 1101 | 4 |
首轮r₀经c₀或c₂可达，r₁经c₂可达，r₃经c₀可达；r₂始终没有入弧。第二轮删去s→c₀、s→c₂，再插入s→c₁、s→c₃。r₀因此由1变0，若漏删便立即给出错误答案。
这里真实发生12次更新和16次查询。一般直接归约的总费用是
这已经是一项按费用传递的归约，但P若是n⁵，直接公式还不能反驳三次时间猜想。必须继续处理预处理项。
什么保证没有被本构造使用
弧方向不可改成无向边。无向图中，两个行顶点可能借未激活的列互相联通，产生不是某个单独Mᵢⱼvⱼ支持的路线。仅有无向连通结构不能直接替代这里的有向可达接口。
接口属于全动态有向边更新：向量变化既插边也删边。只插入结构、只删除结构、预先知道全部活动区间的离线结构，均不是这个直接归约调用的求解器。下面的下界也不会自动覆盖它们。
逐位扫描每行可在O(n²)时间算一个Mv，总计O(n³)。将每行和向量打包进w位字，逐字AND并判断是否非零，总成本可写成O(n²⌈n/w⌉+n²)；w=Θ(log n)只省对数，不与真次三次猜想冲突。拿n位大整数的一次AND当常数操作，会改变字宽。
推论与应用
用小块支付高次预处理
下面证明上面的更强后果。将ε缩小到0<ε≤1，并把c放大到至少2。选b=⌈n^α⌉，0<α<1稍后确定。将M划成g×g个b×b块，其中g=⌈n/b⌉；边界不足b时补零。为每块Mxy建立一份2b+1点的动态结构，初始只有其列到行弧。
第t个完整向量到达后，将它切成g段vᵗᵧ，边界补零。对每份块结构更新当前源边，并查询b个行输出，得到Mxyvᵗᵧ。再对同一行块x的所有y逐位取或：
式子由按列块划分原来的存在量词得到。虚拟零行列没有贡献；最后只保留原n行。必须完成这些输出并交付后，才接收下一向量。各块虽然并列存在，也只接触当前vᵗ，没有提前看到vᵗ⁺¹。[1, §2.1的分块思想]
有O((n/b)²)份结构，预处理为
每轮每块至多b次更新、恰b次查询；n轮合计O(n³/b)次。若两种操作均为O(b^(1−ε))，其总成本为O(n³b^(−ε))。读取和合并各块的b位结果还需O(n³/b)，这笔费用不能算成“已经回答所以免费”。构造块和读入M的O(n²)被以上费用覆盖。
于是全部时间为
取
取整只改变常数。三个n的指数分别为2+α(c−2)、3−αε、3−α。第一项小于5/2，后两项严格小于3，故存在固定正余量。即使再乘一个log n，也可将余量减半吸收。
例如c=5、ε=1/3，α=1/12，三个指数为9/4、107/36、35/12。最大者107/36=3−1/36；留一半余量支付放大等对数费用，仍得到O(n^(3−1/72))。附件使用精确分数输出这份账本，没有将浮点四舍五入后的“接近三”当作证明。
这个论证只需要每份结构处理多项式长序列：n=b^(1/α)至常数因子，而1/α是固定常数。其工作量可能含许多轮查询，即使某次向量与前轮相同、没有更新，也仍按查询数收费。若所引摊还保证只覆盖某种受限更新次数，必须先确认能覆盖这里的真实序列。
概率与预处理的最后两条边界
随机结构可为每个块建立O(log(n+2))份独立副本，同一更新发送给所有副本，对每个查询位取多数。对固定矩阵和固定向量序列，各份副本看到的更新与查询位置完全相同，且不由随机答案决定；若单个查询错误概率至多1/3，独立重复可将每个多数错误压到1/O(n³)。全部查询数为O(n³/b)，并合后总错误可压到1/3。副本的预处理、更新、查询及多数统计全部带同一个对数倍率，前面的正余量足以支付。
这里没有要求动态结构抵抗观察内部随机位的对手，也没有把“每次失败至多1/3”直接当成“全程失败至多1/3”。对只有特定自适应保证或期望时间的结构，应重新匹配模型，不可只搬复杂度数字。
c必须是固定常数。若预处理为2^N，把b取成n的固定正幂仍然产生超多项式费用；本证明没有排除这类结构。事实上可以枚举全部2ⁿ个向量，预存每个Mv，此后查表很快，但这正是猜想总时间不允许免费使用的表。
可执行终点与研究状态
综合练习要求在上面四轮输入上运行直接图和b=2分块图。分块共有四份五点图，实际24次更新、32次查询和32次逐位合并；图变小并不保证这个微型样例跑得更快，分块的目的在于渐近上压低高次预处理。
附件的pull/submit协议在提交本轮完整正确输出前拒绝再次pull，另有真正BFS基线供逐查询核验。协议是教学接口检查，不是防止Python反射的安全沙箱。BFS成本也照实记录；假想的快速结构仅出现在明确标注的指数预算中，程序没有声称实现它。
截至2026-10-09，应将本页原始OMv与带hint版本分开。2026-10-05的Alman–Vassilevska Williams预印本报告改进三种细长矩形hinted任务；那里预先给出包含候选向量的提示矩阵，再揭示索引，信息接口不同。该文明确将无hint的普通OMv列在未涉及的问题中。[2, pp.8、61] 因此不能把相关标题中出现“OMv”当成原始猜想已被推翻。
参考资料
- Monika Henzinger、Sebastian Krinninger、Danupon Nanongkai、Thatchaphol Saranurak，Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture，STOC2015扩展稿，§1 Conjecture1.1、PDF p.3；§2.1 Definition2.1、Theorem2.2及分块引理，pp.10–14。本页只证明源点可达这一完整后果，不将文中的全部动态下界一并移入。
- Josh Alman、Virginia Vassilevska Williams，Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs，2026-10-05预印本，PDF p.8 hinted接口、§6未涉及问题。仅用于截至本次写作的模型区分，不代替原始OMv猜想定义。