- Introduction
- optimization vs. decision problem
- mapping reducible vs. Turing reducible
- #P complete
- strong NP-completeness
- FPTAS
- BPP
- NPI
- Reference
Introduction
这一篇内容将梳理和辨析几个复杂度理论中比较重要和略显进阶，同时又容易混淆或认识错误的概念。这些内容主要是为了下面我将写的物理中的计算理论系列做一个基础（如果我不弃坑的话），而更基础的部分，诸如 SAT is in NPC，NP vs. P 等概念就不再赘述了。这篇笔记里的概念可能相互联系也没那么大，前后也没太多逻辑，还是想哪说哪的意识流文章，但核心还是围绕着 NP 这一时间复杂度展开的。
optimization vs. decision problem
我们通常讨论的复杂度，比如 P 和 NP，都是基于判别问题的，也就是输出只能是 Yes 或 No。这种问题本身就简单，同时又具有理论上的简洁性，因为我们可以把输出为 Yes 的输入字符串看作一个集合，这也正是对应判别问题图灵机接受的语言。因此复杂度问题的分析很大程度上过渡到了更熟悉的形式语言的分析。举个例子，大家经常说 traveling salesman problem (TSP) 是一个 NP 完全问题，其实这指的不是找到一条总距离最短的路径是 NP 问题，而是指的以下问题是 NP 完全的：
对于给定输入图 G，是否存在一条路径总权重小于等于 k？
如参考 [1] 中所说，对于任意优化问题，都可以给出对应的判别问题，只需把求最小（大）值问题，改为是否取值可以小于（大于）等于某值的判别问题。下面可以看到在图灵可约性的意义下，优化问题 \(P_O\) 并不比对应的判别问题 \(P_D\) “难”。
假设 \(y=f(x), \max y\) 是一个优化问题，严格的说，优化问题输出的是可以使得函数 f 最大的 x 的取值。与之对应的还有所谓的 evaluation problem，这种问题输出的是最大的 y 值本身，而不具有 x 取值的信息，这种问题定义为 \(P_E\)。
mapping reducible vs. Turing reducible
计算理论特别是复杂度理论中常见的问题“约化”，多是基于的 mapping reduce。假设存在图灵机可计算的函数 \(f(x)\), 也即存在一个图灵机，输入纸带为 x，输出为 \(f(x)\)， 使得 \(\forall x \in A\iff f(x)\in B\)。我们就称语言 A mapping reducible to 语言 B，记为 \(A\leq_m B\)。当我们把可计算函数 f 进一步限制为需要存在图灵机在多项式时间实现时，就退化到了复杂度理论中最常见的“归约”定义。注意到该定义是针对语言的，也即只能应用于判别问题的约化。如果我们想要更直观的描述更广义的问题的归约，就需要引入 Turing reduce 的概念。
首先需要定义 oracle，所谓 oracle 就是一个超现实的黑箱，也即对于指定问题 P，总是可以给出正确答案的机器记为 \(M^P\)。为了复杂度分析的需要，当然也可以限制 oracle 在常数时间或多项式时间给出正确输出，反正是做梦，怎么假设都行。连停机问题都可以解决（但即使引入 oracle，总是还存在不能解决的问题）。如果问题 \(P_2\) 有 oracle \(M^{P_2}\)，将其作为 subroutine 可以解决问题 \(P_1\) 的话，就称 \(P_1\) is Turing reducible to \(P_2\)，记为 \(P_1\leq_T P_2\)。很明显，图灵归约性是映射归约性的扩展，也即 \(A\leq_m B\rightarrow A\leq_T B\)。这样一个定义超出了形式语言归约的范畴，可以用来对任意类型的问题进行归约。对于上节提到的优化，评估和判别问题，直观的我们有 \(P_D\leq_T P_E\leq_T P_O\)。事实上根据 [3] 中关于 NPO 复杂度类（优化问题类比 NP 的复杂度类）的定义和 [1] 中的证明，我们有以下结论：
若 \(P_O\in NPO\) 且优化问题的取值是整数，同时 \(P_D\) 是 NP-complete, 则: \(P_D\equiv_T P_E\equiv_T P_O\).
换句话说，某种程度上，优化问题，评估问题和判别问题难度“相同”。[1] 中的证明简洁清楚，也很有趣，感兴趣的读者可以自己去阅读，我就不再画蛇添足复述一遍了（主要是懒）。
#P complete
除了从判别问题向优化问题方向的扩展，也即从是否存在\(x ~s.t. f(x)\leq k\) 到找到 \(x~s.t. ~\min_x f(x)\), 我们还有另一个扩展方向，即把判别问题中的有没有替换为有多少。期望的输出也自然地从是否变成了一个具体的数字。也即计算 \(\vert \{x\vert f(x)\leq k\}\vert\)。这类问题被称为 #P 问题。而 #P 完全自然指的是在 #P 中，且可被所有 #P 问题在多项式时间归约的问题。其中的基石问题，自然是 SAT 的 count 版本 #SAT，也即存在多少不同的赋值方式使得对应逻辑表达式为真。
#PC 最典型的一个问题，是图的 pefect matching 的数目。可以证明对于平面图，该问题 in P （参考 FKT algorithm，我也将在后续文章详细分析），但对于一般的图该问题是 #P 完全的。这一问题的神奇之处在于，其对应的判别问题是否能找到 pefect matching 是可以在 P 时间解决的“简单”问题，但其 sharp-P 版本依旧是 #PC，也就是某种程度上 #P 中最难的部分。换句话说，不是只有在 NPC 中判别问题对应的 count 问题才是 #PC。
strong NP-completeness
所谓的 strong NPC，是指的如果输入是 unary 的方式，该问题还是 NPC。所谓 unary 编码，就是一进制，也即完全按照输入的长度来区分输入数据的大小。这和其他进制有本质区别。举个判断一个数是否为质数的例子（事实上 PRIME is in P，参考AKS primality test，这里仅用 naive 的方式来判定质数，仅为了用例子解释 unary 的概念），给定输入 n，一种做法就是试从 3 到 \(\sqrt{n}\) 的奇数，如果都不能整除 n，则 n 是质数。考虑到数字 n 输入用 binary 编码，则共占据 \(\log_2 n\) 位，而所有算法复杂度的标度都是根据输入字符串的长度定义的，那么所谓 P，其实指的是质数判定算法的复杂度是 \(O((\log_2 n)^m)\)，而我们的 \(\Theta(n^{1/2})\) 复杂度的算法其实是指数级的。但如果输入编码换为 unary，情况则完全不同了。此时数字 n 占据的输入位也为 n，我们 naive 的质数判定算法就是 P。为了区分，我们把这种输入编码为 unary 时，或等价的说参考标度不是输入字符长度而是输入数字数值大小时，此时的 P 被称为 pseudo polynomial algorithm，即伪多项式算法。明白了 unary 编码的特点，也就理解了另一个 SNPC 的等价定义，所有数值参数的大小都被输入长度的多项式级限制时，仍是一个 NPC。事实上，整个 strong NPC，和这些定义，都是想解决关于算法复杂度定义的微妙之处－－有时候，分析算法复杂度随输入字符长度的标度，可能不是最自然的方式。
与 strong NPC 相对的 weak NPC，则是具有 pseudo polynomial algorithm，这样一旦数值都被限制在输入长度的多项式级，整个算法也被限制在了输入长度的多项式级，也即此时问题已不在 NPC。参考 [4] 中可以使用动态规划解决的部分和 PARTITION 问题，就是一个 weak NPC 的例子。
FPTAS
对于 NP-hard 的优化问题，我们可以提出一些多项式时间的近似算法使得我们给出的值 \(C\)，满足 \(\vert{C-C_{OPT}}\vert\leq \epsilon C_{OPT}\)，其中 \(C_{OPT}\) 是问题的真实最优解的值。这样一种近似算法，我们称为对应优化问题的 \(\epsilon-\)近似。对于 NPO 问题（对应 NP 判别问题的优化问题），我们可以定义 APX 的复杂度。一个存在多项式时间 \(\epsilon-\)近似算法的问题，被认为在 APX 之中。类似的也可定义 APX 完全和 APX 困难，参考 wiki。
如果我们能找到一系列的算法给出\(C_\epsilon\)，使得我们能够控制 \(\epsilon\) 的精度，也即近似的准确度，我们称这类算法为一个 approximation scheme。如果这一 scheme 对于不同的近似程度 \(\epsilon\)，算法关于问题的规模总是多项式复杂度的，则被称为 PTAS (polynomial time approximation scheme)。需要注意 \(P\neq NP\) 会使得 PTAS 是 APX 的严格子集，也即 APX 完全问题不存在 PTAS。特别有用的是，如果这一组算法的时间复杂度同时为 \(1/\epsilon\) 的多项式级，我们称该问题具有 FPTAS (fully polynomial time approximation scheme)。
可以证明不是所有的 NP-complete 问题，都具有 FPTAS。也就是说，在近似算法的语境下，不同的 NPC 问题并不等价。更严格的说，对应 strong NPC 判别问题的值域在整数的优化问题，不具有 FPTAS。这一结论反证法很好证明，因为优化目标取值是离散的，只需取 \(\epsilon\) 是最优解最大可能值（根据 strong NPC 的定义，这一值被多项式级所限制）倒数的一半，那么整个近似算法相对于输入长度都是多项式级的时间复杂度。而此时给出的近似绝对误差已经缩小到了 \(1/2\)，而最优解可能值的间隔为 1，事实上此时的近似解只可能是精确解。除非 P＝NP，否则不可能。更形式化的证明，可以参考 [5]。
以上讨论均针对整数取值的优化问题。对于实数的优化问题，strong NPC 并不能保证不存在 FPTAS。具体点说，取值限制在整数，本来是 weak NPC 的问题，当取值限制放宽到有理数域，对应的问题很可能变成 strong NPC，但相应的 FPTAS 可能还能继续用。这也不是意料之外的结论，如果注意到前边关于 strong NPC 一定不存在 FPTAS 的证明强烈的依赖于整数取值的间隔来将近似唯一的固定在确定值上，这方面的讨论可以参考 [6]。
BPP
回到判别问题，如果存在依赖随机数的多项式时间算法，可以给出超过1/2的成功概率，那么可以证明，该算法可以在多项时间使得输出的成功概率指数级的提高（只需独立运行该算法几次即可），这种问题复杂度被记为 BPP (bounded-error probabilistic polynomial time)。而 RP 复杂度，则是回答 NO 的成功率是 1，而回答 YES 的成功率大于 1/2。与之对应的问题，就是常用的随机数的素性测试算法。当然与此类似，我们也可以定义 coRP 类。
关于 BPP 最重要的一个未决猜想就是 \(P=BPP\)，也就是如果可以多项式时间给出超过一半的概率正确的答案，那么总能在多项式时间给出严格正确的答案，这一 conjecture 和 \(P\neq NP\) 一样，还未得到证明。关于该证明可能的路线图，可以参考 [8]。正如 wiki 所说，处在 BPP 还未发现 P 算法的问题正在逐渐减少，特别是 PRIME is in P，无疑是支持 \(P=BPP\) 的一个有力证据。但目前仍有 BPP 问题尚未发现 P 算法，比如Polynomial identity testing。这一问题是判断给定某多项式是否为0，如果通过系数加法乘法暴力展开，来分析各同类项系数是否均为0，该算法需指数时间复杂度。而相反，如果我们只是给定一族随机值 \(x_i\)，来计算多项式的值，该值为 0 明显告诉我们，这个多项式恒等于 0 的概率大于一半。关于 PIT 问题复杂度和严格化的更多讨论，可以参考 [7]。另一方面，如果证明存在对数长度种子的“好的”随机数产生器，就可以证明 \(BPP = P\)，参见 [9]。
NPI
Ladner 定理是说：
如果 \(P\neq NP\)，那么存在语言处于 \(NP-P-NPC\)。
该定理通过类似对角线证明方式的惰性构造，人为地构造出了既不在 P 中也不能被 SAT 归约到的语言 （不是 NPC）。具体细节可以参考 [10]。
这样的问题被称为处于 NPI (NP-intermediate)。当然没有任何“自然”的问题被证明处在 NPI，否则我们就立即解决了 \(P\neq NP\) 的假设。但有很多问题我们怀疑是处在这一类中，最著名的就是和密码学高度相关的离散对数。相关疑似 NPI 问题可以参考 wiki 的列表。
Reference
- Optimization version of decision problems
- “NP-complete” optimization problems
- Decision problems vs “real” problems that aren’t yes-or-no
- Strong NP-Complete Results: Motivation, Examples, and Implications
- FPTAS lecture
- On Strong NP-Completeness of Rational Problems
- Randomized Algorithms Lecture
- Proof Strategies on P versus BPP
- pesudo randomness and P vs. BPP lecture
- Two proofs of Ladner’s Theorem
EOF