从优化阈值到最优见证

二分回答“最好能到几分”，前缀恢复回答“由哪些选择得到这一分数”。知道赛场最高分，并不能仅凭分数写出获胜者的名单。两个阶段共享可行性验证，却承担不同的输出义务。

整数目标让“精确停在哪里”有明确含义。候选值的数量可能是指数级，但写出其编号只需多项式位；二分利用这个差别。逐个尝试每个数值会重新花掉指数时间。

价值为 14 的背包见证 ​

给三件 0–1 背包物品 $(w_i,v_i)=(4,10),(3,8),(2,6)$，容量 $W=5$。空集可行，所以 $D(x,0)$ 为真。取上界 $U=10+8+6=24$，二分轨迹为：

于是最优值为 14。接下来先试“不选第一件”：余下第二、三件在容量 5 内可以达到 14，故第一位为 0。再试“不选第二件”：只剩第三件，价值至多 6，不能达到 14，故第二位为 1，剩余容量改为 $5-3=2$，剩余阈值改为 $14-8=6$。最后试不选第三件，空集达不到 6，故第三位为 1。输出 011，总重量 5、总价值 14。

这是背包自身的阈值自归约：每次删除正在决定的物品，选入时扣除重量与价值，实例仍是同一背包阈值问题。若某件重量超过剩余容量，有解不变量迫使试排除为真。剩余阈值非正时，非负容量下空集即达到要求。零重量物品也只能处理一次；表里的物品编号是身份，不能合并重复物品后丢失可选次数。

查询和位账必须同时给出 ​

二分阶段在首次可行性询问之后，至多再用 $\lceil {\log }_2(U+1)\rceil$ 次询问；$U=0$ 时不进入循环。若最大见证长度为 $p(N)$，前缀恢复至多再用 $p(N)$ 次扩展询问，因为已知阈值 $t$ 有解，无需重复建立存在性。背包的固定 $n$ 位选择则恰好再用 $n$ 次上述试排除查询。

每条阈值查询长度为 $O(N+\log (U+2))$；一般前缀查询再加 $O(p(N))$。中点、阈值比较与端点更新操作的是 $O(\log (U+2))$ 位整数，必须按 位复杂度理路位复杂度Bit complexity · Bit operation complexity固定有限编码与逐位计算模型后，以基本位操作数衡量算法成本，并将中间数的实际位长计入每次算术运算。收费。若转交 NP 完全 oracle，归约自身的运行时间和输出长度也要乘进总账。因此“对数次判定”只说明调用层节省，不保证判定子程序便宜。

本例 $U=24$，初问一次、二分五次、见证恢复三次，共九次黑箱调用。把所有价值乘以 $2^b$ 后，位长只增加 $O(b)$，二分迭代增加 $O(b)$；若从 0 一直线性试到 $24\cdot 2^b$，则付指数于 $b$ 的轮数。两种方法得到同一整数答案，成本却不同。

不适用的接口 ​

若目标可取任意实数而只给比较 oracle，不能假设有有限二进制最优值或通过有限二分得到精确解。例如无限集合可能只有上确界却没有最大元；本页的有限见证条件原本排除了这一点。有理目标若要整数化，须先给统一分母或可证明的分离界，并计算表示长度，不能把整数版本原封不动迁移。

若黑箱只近似回答阈值附近的可行性，真假单调边界会出现未知带；若目标可能负值，首次询问 0 也不能再用来检测空可行集。两种变体都需要新契约。仅返回最优值的黑箱并不自动知道哪个见证达到它，一般前缀接口的必要性仍然存在。

本页把三个责任分开：验证关系定义什么算可行；整数目标与已编码上界支撑精确二分；前缀或问题特有自归约恢复对象。由此可以解释精确优化为何常与阈值判定相连，而无需把优化任务本身写成 NP 语言。

背包的实际阈值 oracle 可以用 容量动态规划理路复杂度类 PP · Polynomial time能由确定性算法在输入长度的多项式时间内判定的语言集合。实现，但 $O(nW)$ 是数值容量账单，二进制输入下仍可能很大。旧有 FPTAS 缩放证明理路通过缩放构造 FPTASFPTAS via scaling · value scaling FPTAS通过缩放并向下取整数值，把背包的伪多项式动态规划转为对输入规模与精度均多项式的方案。改变的是允许误差与状态范围；它没有把精确判定 oracle 免费变成多项式时间程序。共同终点同时复算九次调用、完整 DP 行和缩放参数，要求解释三种接口的不同承诺。