# 去掉对数：一般证明与研究记录

一般三次方上界已经证明。建议先读[独立的一般证明](research/proofs/cubic-bound.zh.md)；[较早的乘积界证明](complexity.zh.md)解释原有对数来源，本文保留走到新证明之前的子类、归约和失败路线。

## 1. 当前准确结论

对道路格数为 $N\le n^2$ 的诱导四邻接森林，候选列表算法已证明

$$
W\le(5n-3)N,\qquad T=O(n^2+m+nN)\subseteq O(n^3+m).
$$

当 $m\ge n-1$ 时，水平道路条带给出匹配下界，因而

$$
T_{\rm worst}=\Theta(n^3+m).
$$

**一般的对数缺口已闭合。** 新证明使用全部历史的逐行最早星心、共同切口、分量内参考类，以及按一个标签轴长分组的容量二分配，得到

$$
\widetilde M_h\le4|G_h|.
$$

关键改进是固定同早端的原查询轴像，把参考晚轴当作第二条轴。两份实际有限轴段已足以迫使副本间距超过标签轴长，不需要高幂、直轴或无限物理延长。方向 A 的连通并不交命题虽然被反例否定，常数容量仍然成立。参见[反例与初稿](research/proofs/reference-capacity.zh.md)及[完整一般证明](research/proofs/cubic-bound.zh.md)。

下文的“容量”指把标记分配给允许使用的道路格并限制每格接收次数；“支付”指用已有总量上界的计数覆盖标记。这些是证明工具，不是程序新增步骤。第 2—5 节保留历史推导及原方向；它们的局部限制和反例仍有意义，但不再表示算法的一般复杂度尚未解决。

本文把结果分成三类：

- **已证：** 有一般推导，写明适用条件。
- **已否定：** 有满足相关条件的具体反例或参数族。
- **未证：** 只是充分条件、猜想或可继续检验的思路。

有限搜索没有找到反例，不等于已证；辅助计数有反例，也不等于算法有反例。

## 2. 在一般证明之前得到的输入子类

下表各项都是独立的充分条件，不要求同时满足。查询树始终指最后一次仍有候选存活的完整位移树；最后清空候选的失败新点不放入这棵树。

| 条件 | 已证扫描界或结论 | 证明思路与入口 |
| --- | --- | --- |
| 查询树或每个道路分量的叶子数有统一常数上界 | $W\le N+3(n-1)\sum_C|C|\min(L_T,\ell_C)$ | 每条根叶链对固定目标只贡献线性次成功；交换查询与宿主可取两侧叶数的较小者。[根叶链证明](research/proofs/complexity-chains.zh.md) |
| 道路分量都是路径；或有效查询是一条可从两端交错增长的路径 | $W\le(6n-5)N$ | 上一行的直接推论。旧方向字符串论证保留在[路径证明](research/proofs/complexity-paths.zh.md)。 |
| 每个道路分量到某条主路径的树距离至多为固定常数 $r$ | $W\le(2r^2+2r+1)(6n-5)N$ | 将枝杈命中投影到主路径，控制短连接的可能性。[根叶链证明后半部分](research/proofs/complexity-chains.zh.md) |
| 每个道路分量只有 $O(n)$ 个分叉点，枝长任意 | $W\le(6n-5)N+\sum_C|C|B_C$ | 首次出现查询分叉后，成功位置必须映到宿主分叉。[分枝证明](research/proofs/complexity-branches.zh.md) |
| 先完成查询直径及查询根到它的连接，再增长删除直径后剩余的路径挂枝 | $W\le(10n-7)N$ | 已完成子模板给挂枝的两侧提供平衡约束。访问顺序是必要前提，尚不能删去。[分枝证明](research/proofs/complexity-branches.zh.md) |
| 查询的每个非空水平平移交集都连通 | $W\le2nN$ | 对固定水平标签，同一查询势能类型的标记注入道路交集。包含任意根、任意访问顺序的直主干直齿梳形查询。[标签证明第 7 节](research/proofs/complexity-labels.zh.md) |
| 每对相邻行的竖边列位置，每个非零差值的重数都至多为固定常数 $b$ | $W\le[(b+2)n-b]N$ | 用局部竖边限制重复早端，再分配完整早前缀。这允许稠密道路和超过线性数量的分叉。[标签证明第 15 节](research/proofs/complexity-labels.zh.md) |
| 相关标签平移词的幂次数有统一常数上界 | $W=O(nN)$ | 按树轴最短周期和资源投影分组；幂次数控制资源重复使用。无非平凡幂时可取 $W\le(4n-2)N$。[标签证明第 20、27 节](research/proofs/complexity-labels.zh.md) |

其中 $L_T$ 是有根查询叶数，$\ell_C$ 是道路分量的无根叶数，$B_C$ 是道路分叉点数；单点树的叶数取一。两棵树的叶数可以同时很大，所以第一行不解决一般情形。

还有一个直观的限定族：同一张图内，不同高度梳层的总成本可按总齿高共同支付。关键是按一个候选能存活多久收费，而不是在每个前缀上重新领取整幅道路的预算。它解释了为什么“混合很多高度”未必产生对数下界，完整计算见[混合层高证明](research/examples/comb-scales.zh.md)。

关于单棵梳形树为何在线性次筛选后仍有平方个候选，以及按所述顺序访问后任意继续查询为何仍不超过三次方，见[梳形树问答与图示](research/examples/comb-candidates.zh.md)。该文补充固定常数倍模板的精确计数，并区分单前缀候选数与全部筛选费用。

## 3. 保留完整前缀的标签路线：历史归约及其闭合

### 3.1 从成功检查到一对早、晚查询点

每个候选至多失败一次，所以全部失败检查至多为道路数。对成功检查，固定道路目标格和查询行，把最早成功点记作早端 $e$，同组后来的成功点记作晚端 $f$。初始零位移不参与选星心。

定义

$$
h=f-e=(0,d)\ne0,\qquad a=v-f.
$$

两次成功给出的条件是

$$
a+P_{t(f)}\subseteq F,\qquad
a+h+P_{t(e)}\subseteq F.
$$

定义标签交集

$$
G_h=F\cap(F-h).
$$

由于早前缀包含在晚前缀里，整份早资源都在交集中：

$$
S_{a,e}=a+P_{t(e)}\subseteq G_h.
$$

这比“根到早端的路径存在”更强。过去多次失败的计费，恰恰丢掉了完整前缀中的其他分支。

记这种只按行分组的标记数为 $M_h$，则

$$
W\le(n+1)N+\sum_hM_h,\qquad
\sum_{d\ne0}|G_{(0,d)}|
=\sum_r k_r(k_r-1)\le(n-1)N.
$$

这里 $k_r$ 是第 $r$ 行的道路数。原充分目标 $M_h\le C|G_h|$ 现已由一般证明实现，常数可取四。以下保留取得这一结论之前的逐步归约。

### 3.2 为什么完整早资源是有用的

**已证：早端互异的标记子族有单位容量。** 对任意标记子集，选早端最晚的一笔。它的完整早前缀已经包含这个子集的所有不同查询早端，因此这一份资源本身就有不少于子集标记数的点。Hall 条件成立。

这里仅要求查询早端互异，源可以不同。反之，同一早端可能对应许多源，不能不加处理地使用此论证。

还有若干已证的局部容量：源共线时可单位分配；全部完整资源位于一条简单路径内时容量至多四；轴投影很短或早端种类很少时也有常数容量。[标签证明第 13、17、21、24、27 节](research/proofs/complexity-labels.zh.md)给出准确条件。

### 3.3 共同切口与树轴筛选

不同查询交集分量的标记具有真实时间反序：若一个早端更早，其晚端反而更晚。利用最晚早端确定共同切口，可把已完成或两份前缀相交的标记一次支付；留下的两份相关查询子树不相交，所有晚源仍匹配同一个完整前缀。

标签交域上的平移还对应一条树轴。将沿轴的方向词写成最短词的幂，记最短周期长度为 $p$、幂次数为 $q$，则标签沿轴的长度是

$$
\ell=qp.
$$

这里是树路径的边长，不应与格点中水平坐标差一概混同。不同“查询轴类”记录查询侧不同的平移轴；“实际参考轴像”还包含它在宿主树中落在哪里的信息。

已有容量规则支付了低幂、路径交域、单点轴交、少早端，以及短轴跨度的部分。对其他分量还可支付四个长早轴类。剩余标记因而必须同时处于高幂、分叉交域、多长轴类的困难部分，每份资源含有至少两个周期的轴跨度。

### 3.4 参考类与每源点块：最终已证的归约

在所选同周期共轭类中，以最晚早端所在类作为参考。参考类的全部标记，包括离轴早端，都可以支付。

每个非参考源都匹配参考晚前缀，以及所有非参考晚端中最早者的完整前缀。两条不同查询轴同时存在，迫使共享同一参考轴像的不同源，沿轴相距超过一个标签长度。因此每源可以领取 $\ell+1$ 个互不冲突的轴点。

**同一参考轴像内，完整共同早树的副本也互不相交。** 但不同轴像的资源会重叠，不能跨像直接相加资源大小。

最短周期为一时，参考轴像的道路交集互不相交，点块成本可跨标签合并。为了避免依赖历史轮数，记最终未付量为

$$
E=E_{\rm curved}
+\sum_h\sum_{a\ {\rm nonref}}\bigl(r_{h,a}-(|h|+1)\bigr)_+.
$$

其中 $E_{\rm curved}$ 是上述筛选后最短周期大于一的标记数；$r_{h,a}$ 只统计同一筛选余项内、最短周期为一的非参考源标记。参考类必须在该余项里重新选择。则已有

$$
\boxed{W\le(12n-10)N+E.}
$$

**当时未受控的余项 $E=O(nN)$ 现已得到。** 它只计实际标记的一个子集，一般标签容量界可直接控制它；不必再对弯曲周期和每源超额分别收费。此前仅有轴类数、交域数或每源点块，并不足以推出这一结论。历史归约见[标签证明第 29—38 节](research/proofs/complexity-labels.zh.md)。

### 3.5 另一个可用限制：标签平移源的死亡位置

每个非参考源匹配参考晚前缀，但其标签平移源在参考早端之前或同一时刻已经失败。否则它的参考早前缀整体落在原交域里，统一的平移关系将迫使它也属于参考轴类。

第一次失败的查询父边，映到宿主后是一条从交域内到交域外的边；未平移的晚源在该边两端仍成功。这保留了完整历史条件，但不同源可能复用同一条边，尚未获得常数重数的费用界。见[标签证明第 40 节](research/proofs/complexity-labels.zh.md)。

## 4. 已否定的路线：具体错在哪里

下表否定的是相应辅助命题。列出的构造都不能被直接当作一般算法的超三次方反例。

| 已否定的加强 | 反例说明了什么 | 保留的有效部分与入口 |
| --- | --- | --- |
| 任意道路森林都能保持原位置补点成为一棵诱导树 | 线性数量、每棵线性大小的路径可以任意两棵都无法连接；扩大网格也无效 | 否定这一补点归约；这些路径森林本身仍属于三次方上界已证子类。[反例、图示与证明](research/examples/tree-extension.zh.md) |
| 模板超过线性大小后，候选必降至线性个 | 合法梳族中，模板和候选都可远大于边长，乘积仍达到一般界同阶 | 单前缀乘积界仍正确。[多尺度梳形构造](research/examples/comb-scales.zh.md) |
| 对全部历史成功位移直接使用静态平行四边形禁形 | 历史成功来自不同完整前缀，其并可含非退化平行四边形 | 主证明必须固定同一完整模板。[局部计费反例](research/examples/local-obstructions.zh.md) |
| 每次成功一定增加包围盒或副本并集 | 两者都可连续不增长，仍有合法成功检查 | 不能逐次向“新占用空间”收费。[前缀重叠证明](research/proofs/complexity-overlaps.zh.md) |
| 一般查询前沿总数是道路数的常数倍 | 同根诱导网格树的前沿数可达 $\,\Theta(nN)\,$ | 前沿事件存在完整前缀冲突；直接实际匹配量没有同样反例。[前沿反例](research/proofs/complexity-overlaps.zh.md) |
| 只用历史第三长臂容量支付重复收费 | 容量可恒为九，收费随参数无界增长；候选转移也未增加该容量 | 候选死亡切口与短早臂窗口仍有效。[分枝证明末节](research/proofs/complexity-branches.zh.md) |
| 每笔标记只用自己的根到早端路径，就有统一常数容量 | 二次方个真实标记可以拥挤在线性大小的路径并里 | 必须允许使用路径外的完整早前缀。[标签证明第 9 节](research/proofs/complexity-labels.zh.md) |
| 关联图无环；或资源连通就能分开类型与重复早端 | 关联图可以成环；实际资源连通分量可同时有多类型和重复早端 | 宿主道路无环不能自动传给辅助图。[标签证明第 5、8、18 节](research/proofs/complexity-labels.zh.md) |
| 直接相加各势能类或各轴像的资源并 | 复用会导致无界高估；横竖取较小预算也无法普遍修复 | 单类注入、同像内不交仍正确。[标签证明第 10、22、39 节](research/proofs/complexity-labels.zh.md) |
| 整个标签交域可按标签无限平移并保持森林 | 不同离轴枝在远副本对齐后可以成环 | 单份严格切口资源满足更强前提，仍可无限延长为森林。[标签证明第 34—35 节](research/proofs/complexity-labels.zh.md) |
| 每源点块已支付全部标记，可以删去超额 | 深钩和二维梳状族留下真实超额 | 这些超额仍有显式单位分配，说明规则不够强，并非算法失败。[标签证明第 38—39 节](research/proofs/complexity-labels.zh.md) |
| 每条失效出边只需承担常数个剩余源或常数超额 | 现有四类、参考类和点块付款之后，同一条边仍可承载线性多个源及无界超额 | 只排除直接按边常数收费，仍可研究共享边之后的资源分配。[十轮研究第 1 节](research/proofs/reference-followup.zh.md) |

例如，最新的二维嵌套梳族可同时满足

$$
N=\Theta(n^2),\qquad
\sum |S^{\max}|=\Theta(n^{5/2}),\qquad
W=\Theta(n^{5/2}),\qquad m=\Theta(n^{3/2}).
$$

它严格否定道路数级别的粗资源大小预算，但实际扫描仍未超过目标三次界。[参数证明](research/examples/nested-combs.zh.md)保留了森林诱导性、真实最早星心、单位分配和移动数的逐项核对。

## 5. 原探索方向及最终去向

以下保留当时提出的方向。现有一般证明已完成算法的三次方目标；其中更强的辅助命题并不因此自动成立。

### 当时合并后的安排与现在的结果（2026-10-12）

新建议与原有 A—E 并不互斥：跨尺度摊还是宏观目标，候选寿命提供计数方式，完整前缀、参考轴类和失效边提供可能使用的结构。下表列出当时的目标及现在的结果。

| 主线 | 与已有路线的关系 | 当前结果 |
| --- | --- | --- |
| 跨尺度摊还与接近饱和时的结构 | 加强 D，用 F 的寿命计数串联全部历史 | 已用全历史标签收费控制总和，排除无界多个尺度都花满预算；没有使用接近饱和的结构分类 |
| 完整早资源与候选死亡 | A 的不交命题已否定，转向标签长度分组；B、C、E 是可组合的工具，F 统一解释费用 | 已证明容量二；有限第二轴引理统一处理全部幂次，再加共同切口及参考类得到容量四 |
| 直接争取三次方并搜索反例 | 新增 G、H，防止把更强的道路数界当成唯一目标 | 已证明更强的道路数乘边长上界；原三次方下界与之匹配 |

**最终采用容量二分组完成了一般证明。** 对 A 的验证先后经历[初次检查](research/examples/reference-components.zh.md)、[十轮研究](research/proofs/reference-followup.zh.md)，最终由[左右早横枝](research/proofs/reference-capacity.zh.md)否定一般不交性。新证明保留“同早端副本间距大于标签轴长”，不要求整个连通资源并不交。

### A. 移除参考轴类后的连通资源不交性：已否定

固定真实共同切口、一个高幂共轭类和所选标记子族；移除最晚早端所在的参考轴类。取剩余完整早资源并的任一连通分量 $U$，连通性包括不同资源之间的单位格邻接。原猜想是

$$
U\cap(U+h)=\varnothing.
$$

**为什么值得检验：** 若同一个查询早端在此分量内重复出现，对应两源在自身宿主轴上相距超过一个标签长度，因为两源还必须匹配另一条参考晚轴。连接它们的树路径属于该资源分量，于是会包含两个相差标签的点，与猜想矛盾。早端便互异，可使用单位容量。

**现在的结论：** 两份合法早资源可分别从共同轴点向左、向右伸展，每份短于标签，连通并却跨过整个标签长度。边长 71、171 个道路点的完整历史反例已独立复核；七层版本还能穿过四类付款和参考重选。它没有重复早端，也没有最终点块超额，故只否定该不交命题。

[十轮研究](research/proofs/reference-followup.zh.md)的原顺序嵌套梳列带证明及轴投影等价引理仍成立。替代路线按标签轴长对资源左端点分组，已经得到容量二：组内早端互异，每个道路点至多参与两个组。有限第二轴引理与全部计费见[一般证明](research/proofs/cubic-bound.zh.md)。

### B. 沿失效边支付每源超额

非参考源已带有一条离开交域的真实边。可以尝试证明：许多源若通过同一边产生大量超额，完整晚前缀就迫使宿主额外占用道路，或形成不允许的第二条连接。

现在已证明：即使经过现有付款，单条边的源重数和未付超额也可无界增长。直接按边常数收费已被排除；仍可研究共享这条边的源能否联合使用其他道路预算。证明见[十轮研究第 1 节](research/proofs/reference-followup.zh.md)。单纯把每源全部早资源大小加起来，也已被二维嵌套梳否定。

### C. 跨周期合并弯曲轴的预算：新证明已绕开

对共同最短周期，长轴长度有线性预算；对最短周期一，不同实际轴交不重叠。不同增长周期之间如何共享道路空间，仍没有足够的合并界。

已经有“相关交域只有线性多个”和“周期重复次数总和有界”等结论。但需要的是实际标记数；不能把次数预算误写成所有轴长度或所有资源大小之和的预算。

### D. 直接证明多尺度不能同时饱和：已由全历史界解决

旧一般上界的对数来自不同前缀尺度分别收费。历史高重叠的非平行平移受到几何限制，同方向段的最大重复倍率也已有线性总预算。这说明可以保留已删除候选的历史约束。

仍缺把所有实际成功检查映射到这份预算的方法；仅靠固定参考方向的预算已有反例。见[跨前缀重叠证明](research/proofs/complexity-overlaps.zh.md)。

可以先分析静态乘积界接近饱和时，候选是否必须聚集在少数方向、长重复段或共同分枝结构上，再研究查询增长如何破坏这些结构。目标是让每份结构只领取一次预算。静态梳族已能达到乘积界同阶，因此不能只把单个前缀的不等式改紧；必须用同一候选的存活历史连接不同尺度。

### E. 从高度记录继续缩小剩余收费：局部问题保留

任意查询顺序的若干分叉费用已经支付，剩余可归约为直径或根高度增长时的真实成功量。重复记录有根投影次序、死亡切口和短臂窗口。

尚未控制候选转移的累计重数。记录本身能达到三次方，且可能需要任意多条根叶链；不能改用已否定的一般线性前沿或历史第三长臂容量。

### F. 用候选寿命统一成功检查的摊还：计数方式保留

令 $s(a)$ 为初始道路候选 $a$ 在新位置全量筛选中的成功次数，不计初始零位移与重复访问。候选一旦失败就不再出现，所以严格有

$$
W\le N+\sum_{a\in F}s(a).
$$

这只是换一个顺序统计同一批检查，尚未改进上界。它允许少数候选存活很久；不能额外假设每个候选的寿命都是线性的。可按寿命分层，也可把长寿命候选的完整匹配前缀、首次死亡边和分枝记录一起保留，尝试证明不同寿命层共享一份总预算。B 的平移源失效边和 E 的转移重数，都是这一框架中的具体问题。

### G. 直接争取三次方：更强目标已完成

证明 $W=O(nN)$ 足够，但比原目标更强。**当时带对数上界立即给出的推论**是

$$
N\le\frac{n^2}{\log(n+1)}
\quad\Longrightarrow\quad
W=O(n^3),\qquad T=O(n^3+m).
$$

因此，若只追求原目标，稀疏道路情形已无需新论证，可以集中研究超过这个阈值的情形。可尝试同时给道路、障碍格和边界分配预算，允许使用整个网格的面积。这里没有证明新的稠密图结构，也没有声称每次成功必新增面积；后一个说法已有反例。

### H. 用真实总费用检验反例：改作证明复核

对递归分叉、嵌套重复块、混合周期和不同发现顺序，直接记录 $W/n^3$、实际移动数，以及各倍增前缀区间的费用。需要在同一张图、同一条行走上使许多尺度一起积累大费用；分别为每个尺度另造最坏图没有作用。

有限实验用于挑选值得证明的参数族。只有证明比值随参数无界增长，并控制移动项，才能否定目标总时间；单个大比值、资源大小和过大或多尺度候选很多都不够。本次 A 的实验也保存真实费用与移动数，但不是对这一反例方向的穷尽搜索。

## 6. 怎样判断一个新证明或反例是否真正推进了问题

这份核对顺序也适用于审查现有证明或进一步改进常数：

1. **先确认计数对象。** 是真实候选检查，还是一个可能高估很多的辅助量？
2. **保留完整前缀。** 候选在某点成功，要求此前全部已访问点都匹配。
3. **核对星心最早性。** 任意成功配对未必是当前定义中的标记。
4. **核对诱导森林。** 坐标相邻就自动有边，不能只检查构造者想画出的边。
5. **计入真实移动数。** 树上回走不增加筛选，却仍计入时间中的移动项。
6. **区分证明与实验。** 有限搜索、超过正式边长的数学族检查、原程序核验各说明不同的事。
7. **逐项检查量词。** 同一轴像内不交，不推出不同轴像间不交；固定周期的预算，不允许不加控制地对所有周期重复领取。

[研究目录](research/README.md)提供独立构造证明、代表性输入、输入指纹和验证脚本。