搜索关系与 FNP

关系像验收单：同一张地图可以有多条合法路径，验收单不必预先指定其中哪条。多项式平衡负责保证答案“写得下”，多项式验证负责保证答案“查得快”。两者缺一不可，而“找得快”是第三件事。

前缀询问把一大群候选分成两组。例如当前前缀是 01，询问 010 是否仍有合法补全。回答“是”时可以放心走向这一组；回答“否”时，只有在已经知道 01 确实能补全、且 01 本身还不是答案的前提下，才能转向 011。

变长见证：停止动作不能省略 ​

假设已有准确判定 $E_R$ 的 oracle，即一个暂时把内部求解成本单列的黑箱。令 $N=|x|$，先询问 $E_R(x,\epsilon )$；回答否就返回 $\mathrm{\perp }$。否则置 $s=\epsilon$，反复执行：

1. 用关系验证器检查 $R(x,s)$。若真，立即返回 $s$
2. 若假，询问 $E_R(x,s0)$。若真，把 $s$ 改成 $s0$；若假，把 $s$ 改成 $s1$

不变量是“当前 $s$ 是某个合法见证的前缀”。初次询问建立它。若 $s$ 不是见证，但有某个见证以 $s$ 开头，那么该见证还有下一位，必为 0 或 1；因此排除 0 后可选 1。每轮长度增加一，最多增长到 $p(N)$；此时不变量只能由 $s$ 本身是见证来满足，故下一次验证必然停止。总共至多 $p(N)+1$ 次 oracle 询问、$p(N)+1$ 次关系验证，每条查询长度为 $O(N+p(N)+1)$，写入与验证开销均为多项式。

以一个可手查的小关系为例，对固定输入允许的见证恰为 $\{\epsilon ,10,111\}$。算法在初次存在性询问后直接返回 $\epsilon$。如果删除空串，只允许 $\{10,111\}$，询问前缀 0 得否，转到 1；验证 1 失败，询问 10 得是，下一轮验证 10 成功并返回。若只知道长度上界为 3，却强行补成三位，100 不在关系里；“所有短证书都能随便补零”不是定义。

另一种正规化会显式编码原长度。取 $d=\lceil {\log }_2(p(N)+1)\rceil$，用 $d$ 位长度字段加恰好 $p(N)$ 位数据区，长度不足的尾部必须补零；$p(N)=0$ 时长度字段为空。验证器先读长度字段，检查解码整数 $0\le \ell \le p(N)$，再检查尾部补位并对真正见证运行原验证器；超界长度编码必须拒绝。这样才可合法改成固定长度搜索。上面的直接停止算法不需要做这个转换。

为什么换成 NP 完全 oracle 就够用 ​

固定任意 NP 完全语言理路NP 完全性NP-completeness同时属于 NP 且为 NP-hard 的性质。 $B$。由于 $E_R\in \mathbf{NP}$，存在 Karp 归约理路多项式时间归约Polynomial-time reduction · Karp reduction用一个多项式时间可计算的变换把问题 A 的实例转换为问题 B 的实例。 $h$，使 $⟨x,s⟩\in E_R$ 当且仅当 $h(⟨x,s⟩)\in B$。每次前缀询问先计算 $h$，再调用 $B$ 的判定器，便能执行上述恢复。归约输出长度受其多项式时间约束，因此多项式条查询没有藏入指数长实例。

整套搜索程序是多次自适应 oracle 调用：后一个前缀取决于前一个回答。单次 $h$ 是 Karp 归约，整个恢复过程不是“一次 Karp 映射”。若 $D_R$ 本身 NP 完全，可选 $B=D_R$，从而用原问题的判定器恢复；若只知道 $D_R\in \mathbf{NP}$，没有这一步结论。

原问题永远有解，判定器也可能毫无指引 ​

考虑一个假定难以求逆的、长度保持的多项式时间置换 $f$，关系 $R_f(x,y)$ 当且仅当 $f(y)=x$。置换保证每个 $x$ 恰有一个原像，因此 $D_{R_f}$ 是全部二进制串，判定器永远回答“是”。它没有回答“原像首位能否为 0”。若这类置换存在，验证快且总有解，仍不等于能快速找到解。这是条件性边界例，绝不是已证明某个具体置换求逆不在多项式时间。

仅要求验证快也不够定义 FNP。关系“$x$ 编码整数 $k$，$y$ 恰是 $2^k$ 个零”可在输入加候选的总长度的多项式时间检查，但见证长度不受 $|x|$ 的多项式控制。检查一份巨长答案很快，不会使这份答案变短。

若 P=NP，则上述前缀语言都有多项式判定器，全部 FNP 关系都可在多项式时间求解。反过来，若全部 FNP 关系都有满足本页停机和 $\mathrm{\perp }$ 契约的多项式求解器，给任意 NP 验证关系运行求解器，再检查返回见证，即可多项式判定该语言。这是常说的“P=NP 等价于所有可高效验证的短见证都可高效找到”的精确口径。

SAT 自归约理路SAT 的逐变量见证恢复SAT self-reduction · SAT search-to-decision · SAT 自归约只调用返回是或否的SAT判定器，用逐变量限制恢复总赋值，并分开计算查询次数、查询位长、外层成本与无解终止。提供更直接的实例：不必绕通用计算编码，而是删去已经满足的子句、删去已经为假的文字，把前缀约束继续交给 SAT 判定器。FP 函数接口理路函数复杂度类 FPFP · Function polynomial time · 多项式时间函数明确单值函数的全输入输出契约、写出成本与复合封闭性，并区分FP函数、P语言和FNP关系的选择算法。进一步区分“允许任意一个答案”的关系与“必须输出指定答案”的单值函数。共同终点要求实际写出这两种接口的查询与停止行为。