第八章：搜索、计数与证明

decision problem 只输出一个 bit。构造 witness、计算 witness 数量和证明 no 实例需要不同的复杂度对象。

FP 与 FNP

$\mathsf{FP}$ 是多项式时间可计算函数类。 $\mathsf{FNP}$ 中的 search relation $R(x,y)$ 满足：

$|y|\le |x|^{O(1)}$ ；
$R(x,y)$ 可在多项式时间验证。

搜索 SAT 是典型 FNP-complete 问题。若 $\mathsf P=\mathsf{NP}$ ，通过逐位 self-reduction 可得

\mathsf{FP}=\mathsf{FNP}.

对一般 relation，decision oracle 需要回答“当前前缀是否能扩展为完整 witness”，因此 relation 的结构和归约类型仍需明确。

TFNP

TFNP 进一步要求每个输入都有解。若某个 TFNP 问题在通常 many-one 意义下 NP-hard，往往会导致意外的类 collapse，因此 TFNP 研究由不同存在性原理形成的子类。

典型子类包括：

PLS：有限 potential 每步严格改进，目标是局部最优；
PPAD：有向图中已知一个非平衡端点，寻找另一个端点；
PPP：基于 Pigeonhole Principle 寻找碰撞或未命中元素；
PPA：基于无向图奇度顶点成对出现。

Nash equilibrium 的适当近似搜索与 PPAD 相关。PPAD-complete 不表示问题是 NP-complete；它表达的是 total search 归约下的完整性。

Local search 与 PLS

PLS 问题给出：

多项式时间构造初始解；
多项式时间计算目标值；
多项式时间寻找更优邻居，或确认局部最优。

目标值严格改进且状态有限，保证过程终止。但路径长度可能指数级，因此“每一步高效”和“总算法高效”不同。

这与算法课中的局部搜索直接对应：复杂度问题不是局部最优是否存在，而是能否在多项式步内找到。

Counting class $\#\mathsf P$

对非确定性多项式时间机器 $M$ ，定义

f(x)=\#\{\text{$M(x)$ 的接受路径}\}.

所有这类函数构成 $\#\mathsf P$ 。#SAT 计算满足赋值数量，是 $\#\mathsf P$ -complete。

计数通常比判定包含更多信息。若能精确计算 #SAT，判断结果是否大于零即可判定 SAT。反向不成立于已知方法：SAT oracle 可以找一个 witness，却不能直接汇总指数多个 witness。

parsimonious reduction 精确保留解数量；普通 many-one reduction 只保留是否有解，不足以传递计数复杂度。

Gap 与概率计算

两个 #P 函数之差形成 GapP。随机算法和量子算法的接受概率可以表示为计算路径数量或振幅组合，因此 counting class 是连接复杂度、概率和量子计算的重要工具。

例如 PP 允许多数计算路径接受：

x\in L \iff \Pr[M(x)\text{ accepts}]>\frac12.

PP 的误差间隙可以指数小，因此与 BPP 的常数有界误差具有不同语义。

Proof system

Cook–Reckhow propositional proof system 可视为多项式时间可计算函数 $P$ ，其 range 恰为所有 tautology。字符串 $\pi$ 是公式 $\varphi$ 的 proof，若

P(\pi)=\varphi.

proof length 是主要资源。若存在 polynomially bounded proof system，即每个 tautology 都有多项式长度证明，则

\mathsf{NP}=\mathsf{coNP}.

对 Resolution、Frege、cutting planes 等具体系统证明 proof-size lower bound，可以说明特定自动证明方法必然在某些公式上产生长证明，但不直接解决一般 NP 与 coNP。

Interactive proof

interactive proof 允许计算受限 verifier 与计算不受限 prover 多轮交互。要求：

completeness：真命题有 prover 使 verifier 高概率接受；
soundness：假命题对任意 prover 都低概率接受；
verifier 的时间、随机位、通信量和轮数受限。

经典结论

\mathsf{IP}=\mathsf{PSPACE}

说明交互和随机挑战显著扩大了“高效验证”能力。PCP theorem 则把验证重组为只查询证明的常数个位置，并成为近似困难性的基础。

证明长度与验证时间

短证明不等于容易找到。proof search 需要构造 $\pi$ ，proof verification 只需检查给定 $\pi$ 。同样，NP witness 的存在不提供高效搜索算法。

分析证明系统时需区分：

proof size；
verifier time；
query complexity；
randomness；
interaction rounds；
soundness error。

不同资源交换产生 NP proof、PCP、interactive proof、argument 和 zero-knowledge 等模型。

本章自测

TFNP 的 totality 为什么不直接给出多项式时间算法？
PLS 中局部改进每步高效，为什么总路径仍可能指数长？
普通 SAT 归约为何不一定保持 #SAT 的答案？
PP 的错误保证与 BPP 有什么差异？
polynomially bounded propositional proof system 会推出什么结论？

第八章：搜索、计数与证明 ​

FP 与 FNP ​

TFNP ​

Local search 与 PLS ​

Counting class #P\#\mathsf P#P ​

Gap 与概率计算 ​

Proof system ​

Interactive proof ​

证明长度与验证时间 ​

本章自测 ​