交付一份代数随机化证书 ​

代数随机化与匹配证书路线的终点是一份能被别人独立复算的记录。它包含两个不同方向的结论：某个代入点证明两个电路不相等；一组没有端点冲突的真实边证明图有完美匹配。随机性帮助发现见证，最后的验真不需要相信随机种子。

下载标准库核验器及完整结果JSON。脚本同时包含实际算法和小实例的独立系数展开、排列行列式、匹配枚举等对照。普通运行与 python -O 都执行显式检查；参考随机种子用于重放，不把伪随机发生器的有限状态当成独立均匀模型的证明。

一、冻结电路、域和错误预算 ​

第一项比较 $A=(x+y{)}^2$ 与 $B=x^2+2xy+y^2$。固定底域为 ${\mathbb{F}}_{17}$，变量顺序[x,y]，门按拓扑顺序编号；乘法、加法和减法的前驱编号都必须小于当前编号。输出门为A−B，不允许除法门。

按门传播形式次数得到D=2。取S={0,…,15}，每个坐标用4个独立公平随机位生成，四轮的统一漏检界为1/4096。注意，这是“若实际非零，四次仍看不到差异”的概率，不是“看完四个零之后，恒等式为假的概率”。

先手算点(3,5)：A和B都为13。再把B改成B+x，同一点差为14，是确定的非零见证。附件还输出固定种子的完整逐门轨迹；审核者可不用该种子，直接代入记录里的点。

提交记录应有：全部门、输出编号、素数域、样本集合、D、轮数、每轮点和值、最终状态。D=0时应直接求常数，不要为一个已确定的常数制造随机不确定性。

二、小域失败不能用重复掩盖 ​

在 ${\mathbb{F}}_2$ 上测试x²−x，两个可用点都为零；形式多项式却非零。请给出失败原因以及扩域修复，而非仅把轮数从4改到400。

在 ${\mathbb{F}}_4={\mathbb{F}}_2[\alpha ]/({\alpha }^2+\alpha +1)$ 中，依次代入0、1、α、α+1，点值为0、0、1、1。核验器用两个二进制系数编码这四个元素，乘法后按不可约多项式约简。这是保持特征2的扩域；模4运算有零因子，换成模3则改变底域，都不是同一个修复。

零点界理路Schwartz–Zippel引理Schwartz–Zippel lemma · Schwartz-Zippel lemma · 施瓦茨–齐佩尔引理控制非零多元多项式在独立均匀网格上的零点比例，分清总次数、底域、随机性和有限域函数边界。要求每个输入先固定，并在坐标之间独立抽样。迁移测试改用差x−y：如果两个坐标都使用同一个r，所有轮都会漏检；如果坐标独立，则真实零点率为1/|S|。

三、从边变量得到存在性证据 ​

取四个顶点0、1、2、3的完全图。边表固定按词典序排列：01、02、03、12、13、23。Tutte矩阵理路Tutte矩阵Tutte matrix · 图匹配的Tutte矩阵以反对称边变量矩阵编码一般图完美匹配，证明随机行列式判定，并用隔离权与二进阶主子式提取可验真匹配。的上三角依次填a、b、c、d、e、f，下三角使用同值取负。

在 ${\mathbb{F}}_{17}$ 上，把六值取为(2,8,15,13,16,4)，它们也是下一节整数矩阵的模17像。手算 $af-be+cd=8-128+195\equiv 7$，行列式为49≡15，故图一定有完美匹配。这个行列式的次数是n=4；若改为随机独立取S={0,…,15}中的边值，一次漏检界为4/16，四轮为1/256。

记录中应保存完整边表、每边代入值和模17行列式。非零值证明存在，但还没有列出匹配边。若这次算得零，也不能报告“不存在”；下一节给出实际边集。

四、由隔离权和主子式恢复边集 ​

给六边的权向量定为(1,3,5,6,4,2)，按刚才的已排序边表对齐。此表作为手算输入，不声称它本身是一次均匀样本。真正随机搜索时，每边独立取1..2m，此处m=6，因此R=12。

三种完美匹配的总权依次为3、7、11，最低者唯一。将边变量改成2的权次幂，整数行列式是3717184，二进阶为6；一般图这里是2W=6，不是W=3。

边	wₑ	删除两端点的Dₑ	ν₂(Dₑ)+2wₑ	入选
01	1	16	6	是
02	3	256	14	否
03	5	4096	22	否
12	6	1024	22	否
13	4	64	14	否
23	2	4	6	是

得到M={01,23}后，另开一遍验证：两条边都在原图，每个端点恰出现一次，边数为n/2。这个验证只依赖原图与输出边集，不需要重证隔离事件。

隔离引理保证固定非空匹配族在R=2m时至少一半权表具有唯一最优解。为说明它真被使用，记录须包括“唯一最优为何使最低二进制幂不消去”及“主子式为何能区分属于该匹配的边”，不能只写一次随机运行碰巧成功。

五、必须交出的失败记录 ​

把K₄六边权全部改成1。此时det B=16，每个Dₑ=4，六条边全部满足等式。若程序直接返回它们，就是错误证书；正确实现的端点检查失败，返回RETRY。

再只保留01、02、13、23四条边，权全部为1。图有两个完美匹配，但两个带符号项相消，det B=0。此记录用于核验“零行列式不代表无解”，不能把它删掉只展示成功样例。

给搜索器有限预算t：它每轮重抽权，成功时返回MATCHING及实际边集，耗尽时返回UNKNOWN。只有奇数顶点数等确定结构障碍才直接返回NO。连续随机失败的概率界以图确有匹配为条件，不能从失败日志推导一个不存在证书。

六、结构迁移与位成本验收 ​

原成本与随机扰动 ​

给每条边一个原整数成本cₑ。若有负成本，先对所有边加同一整数使成本非负：每个完美匹配恰有n/2条边，这种平移不改变原目标顺序；一般大小不固定的集合族不能照搬这一步。再用 $(mR+1)c_e+w_e$ 保留原成本的优劣，再说明隔离作用于事先固定的原最优匹配族。如果cₑ数值非常大，把这一复合权再放进2的指数会产生很长的整数；请以最大权数值估算位长，不能只报告原成本的输入位数。

输入顺序与身份 ​

把边输入逆序，再保持“权属于哪条边”的映射不变。参考接口会把图边规范化并排序，传入权向量必须按规范边表对齐；直接将原权数组不动地交给排序后的图，改变的是问题数据。额外测试拒绝自环、重复无向边、超范围端点以及非正整数隔离权。

与求值器无关的对照 ​

电路核验用独立稀疏系数展开作小例子对照，整数行列式用排列展开对照，匹配存在性与最优权用枚举作对照。这些指数方法仅用于小实例验证；正式算法的资源界不能把测试器运行时间混进去。

主提取器使用m+1次基础有理消元。报告算术操作数量、约分后的最大分子/分母位长，以及保留日志的空间；附件max_bits记录实际存储值和消元倍数的位长，不声称统计了Python乘减表达式内部全部临时对象。一般位长上界由子式估计证明，单次小图实测不能替代它。

最终交付至少应有一份非零电路点见证、一份有限域行列式证据、一份实际匹配、两类失败记录和上述三组迁移结果。若只能重复原种子而说不清变量、域和错误方向，尚未达到终点。