证书算法

求解器负责找出结果，检查器负责确认这一个结果。搜索过程可能很复杂，留下的理由却可能很短：一份划分、一个障碍圈，或一对值相等的原始与对偶解。检查器可以完全不关心搜索采取了什么策略，只按输入和证书核对数学条件。

图中两条分支都能被接受：接受奇圈证书确认答案“不是二分图”，接受二染色确认答案“是二分图”。绿色接受标记不表示原问题的答案一定为“是”。

产生二分性证书 ​

输入为有限简单无向图，以编号 $0,\dots ,n-1$ 的顶点和有编号的边表表示。二分图公理库二分图Bipartite graph顶点可分成两个独立侧、且每条边都跨越两侧的有限简单无向图。恰是可正常二染色的图，也恰是不含奇圈的图。这给出两种证书：答案“是”附每个顶点的 $0/1$ 颜色；答案“否”附一条奇数长度简单圈的顶点序列与对应边编号。

求解器用BFS公理库广度优先搜索Breadth-first search · BFS按无权距离分层访问可达顶点的图遍历算法。逐分量搜索，根赋颜色 $0$，每次发现新顶点就赋父亲的反色，并保存父指针和深度。其不变量是 $color(v)=depth(v)mod2$，且每条父边连接异色顶点。若所有原图边都连接异色顶点，颜色表即为证书。

若扫描到同色边 $uv$，沿父链找两条根路径最后共有的顶点 $a$，删去共有前缀，只保留 $u$ 到 $a$ 再到 $v$ 的树路径，最后接上 $vu$。两段树路径内部不交，故形成简单圈，长度为

同色使前两项之和为偶数，减去偶数再加一便是奇数。树路径本身不含非树边 $uv$，所以这份障碍没有把共享根路径来回走两遍。非连通图必须从每个尚未染色的顶点继续启动，否则一个未扫描分量可能藏着奇圈。

两次可以复算的执行 ​

三角形的边为 $01,02,12$。从 $0$ 开始，BFS 先发现 $1,2$，状态如下：

扫描边 $12$ 时发现同色。两条父链交于 $0$，输出“否”与圈 $1,0,2,1$，使用边 $01,02,12$，共三条。另一个输入是路径 $0-1-2-3$，沿路径的深度依次为 $0,1,2,3$；输出“是”与颜色表 $(0,1,0,1)$。这两份输出都不用重新运行 BFS 就能核验。

检查器真正检查什么 ​

对“是”证书，检查颜色表恰好为每个输入顶点提供一个合法颜色，再扫描每条输入边 $uv$，要求 $color(u)\ne color(v)$。由二分划分定义，全部检查通过即可推出答案正确。

对“否”证书，令顶点表为 $v_0,\dots ,v_{\ell }$。检查 $3\le \ell \le n$、$\ell$ 为奇数、$v_{\ell }=v_0$、所有编号合法，以及 $v_0,\dots ,v_{\ell -1}$ 互异。每一步还必须给出有效的输入边编号，并确认该边两端恰为 $v_i,v_{i+1}$。若能正常二染色，沿圈每一步都翻色，奇数步后不可能回到起点原色，所以通过检查的奇圈推出非二分性。

有编号边表允许按边编号常数时间检查端点。若只有未索引的邻接表，逐次在线性长的邻接表里查边，并不能声称每次 $O(1)$；可改为统一扫描核验，或明确加入边索引的成本。在前述表示下，产生与检查均为 $O(n+m)$ 时间，辅助空间为 $O(n)$；颜色证书用 $O(n)$ 个机器字，简单圈也至多用 $O(n)$ 个字。求解器只需在首个冲突处重建一次父链，仍在线性界内。

伪造的三角形颜色 $(0,1,1)$ 会在边 $12$ 被拒绝；闭合游走 $0,1,0$ 虽使用真实边，却只有两步，同样被拒绝。缺少任何一个分量的颜色、使用输入里不存在的边，或声称一个超长数组的长度合法，也都应在接受之前处理。

匹配的可行、不可行与最优值证书 ​

二分图匹配的流归约公理库经由网络流的二分图匹配Bipartite matching via maximum flow用单位容量流求二分图匹配，并从终态搜索同时提取 Hall 障碍、等值割和最小顶点覆盖。给出另一个完整任务：输入合法的左右划分及编号边表，既可问“能否饱和左侧”，也可问“最大匹配有多大”。两种问题的证书规格不同，不能只检查输出边是否互不冲突就宣布最大。

对“能饱和左侧”的答案，证书是一组输入边编号。检查编号合法、左右端点都不重复，且边数等于左点数，即得到一个饱和匹配。对“不能饱和”的答案，证书是左点集合 $A$；检查器扫描输入边自行形成 $N(A)$，要求 $|N(A)|<|A|$。可靠性来自不同左点必须占用不同邻居，候选不足便不可能全部配对。

若答案是“最大值为 $k$”，证书为匹配 $M$ 与顶点覆盖 $C$。除了检查 $M$ 合法，还要逐边核对至少一个端点属于 $C$，最后检查 $|M|=|C|=k$。匹配保证最优值至少为 $k$，而任意匹配的不同边必须由不同覆盖顶点碰到，所以最优值至多为 $k$。这里不需要重新运行求解器，也不需要在检查时重做 Kőnig 定理的构造证明。

例如边集 $a1,a2,b1,c2,d3,d4$ 上，$M=\{a1,c2,d3\}$ 与 $C=\{d,1,2\}$ 证明最大值为三；$A=\{a,b,c\}$ 的邻集为 $\{1,2\}$，证明四个左点无法全部匹配。若输入增加 $c3$，旧覆盖会漏边，旧 Hall 集合的邻集则增至三个点，两份旧证书均被拒绝；新的饱和证书为 $\{b1,a2,c3,d4\}$。

这三类证书均占 $O(n)$ 个机器字，含输入扫描的检查时间为 $O(n+m)$，辅助空间为 $O(n)$。它们的产生可能更贵：逐条单位流增广达到最优值 $k$，加最后一次失败搜索，耗时 $O((k+1)(n+m))$。证书长度、检查成本和产生成本因而是三个不同的报告项。一次拒绝只指出当前证书不合格，例如错误的 Hall 集合，并不能反过来断言饱和匹配存在。

NP公理库复杂度类 NPNP · Nondeterministic polynomial time由正实例拥有多项式长度、可在多项式时间内验证的证书所刻画的语言类。中的多项式见证说明肯定实例存在易检查的理由，并不提供寻找它的算法，也没有同时承诺否定实例的证书。二分性例子强在求解器能找到两类证书，且对应的检查条件都已证明；不能从“答案有证据”推出任意 NP 问题都具有这样的双向求解器。

布尔函数的证书复杂度公理库证书复杂度Certificate complexity of Boolean functions · Boolean certificate complexity用足以强制某个固定输入函数值的最少已知坐标数，分别度量 0-证书与 1-证书。则问固定多少个输入坐标能迫使函数值，证书的对象和量词不同。两者都涉及局部理由，但这里传入检查器的是原始输入、答案和额外见证，不是自动限制其只能查看那些坐标。

最大流最小割定理公理库最大流最小割定理Max-flow min-cut theorem以净跨割恒等式和残量可达集证明最大流等于最小割，并给出独立可检查的最优性证书。给出另一种可用接口：核验流可行、割合法及两者值相等，即可确认最优性，而不必重复增广过程。回到本页，可以先独立写出两类检查器，再让它们处理三角形与路径的证书；最后说明一次接受为何只确认当前结果，仍未证明求解器在所有未来输入上终止。