Karp 归约、Levin 归约、Cook 归约这几个概念有何联系与区别？

我感觉 Karp reduction 和 Cook reduction 的区别还是比较好解释的, 虽然前几年看到这些东西的时候是有点困惑.

譬如说你想证明某个问题 A 是 NP-hard 的, 那么就假定你有求解这个问题对应的语言 L 的 oracle. 为了证明 NP-hardness, 你需要通过查询这个 oracle 来求解 NP 中的任何问题, 而你能用的就是一台确定性多项式时间的机器, 所以现在的问题是你允许怎么查询这个 oracle:

• 只能调用 oracle 一次, 这就是 Karp reduction.
• 可以 non-adaptive 地 (并行地) 查询 oracle 多项式次 这就是 truth-table reduction.
• 可以 adaptive 地 (一次接一次地) 查询 oracle 多项式次, 这就是 Cook reduction.

需要说明的是, 为了便宜起见我们并不考虑把 \mathcal{L} 规约到 \overline{\mathcal{L}} 的情况 (见 [0]). 为什么上面的三种 oracle 调用方式不一样呢? 不妨假设这个问题 A 其实是 NP-complete 的, 那么上述三种查询方式对应的复杂性类分别是 {\sf NP} \subseteq {\sf P}^{\sf ||NP}={\sf P}^{\sf NP[log]} \subseteq {\sf P^{NP}}, 而这三个复杂性类不太可能发生 collapse. 不难看到一些简单的区别:

• 大多数人相信 NP 对补不封闭, 即 {\sf NP} \neq {\sf coNP}, 公钥密码学中作为困难假设的几个问题 (包括 factoring 和格密码相关的) 都在 {\sf NP} \cap {\sf coNP} 里. 注意到 {\sf coNP} \subseteq {\sf P^{||NP}}, 那么 {\sf NP}={\sf P^{||NP}} 会推出 NP 对补封闭, 所以这两个复杂性类不太可能 collapse.
• 我们知道 NP 求解的是判定问题, 如果这个问题在 YES case, 那么我们能够找到一个 NP 问题的 instance 的 witness 吗? 通过一次查询 oracle 显然不够, 标准做法是 adaptive 地查询 oracle 多项式次 (即一个比特一个比特的猜测 witness 到底是什么, 这称作 search-to-decision reduction, 之前在 Stack Exchange 上写过一个更详细的回答: Self reducibility of QCMA problems).

Levin reduction 我不太熟悉, 按照 Arora-Barak 的说法, 还对规约前后的 witness 的大小有要求 (要求都是多项式的). Arora-Barak 举得例子是 PCP reduction, 这里不再展开.

然后举一些 Karp reduction, truth-table reduction, Cook reduction 对于不同复杂性类的例子吧.

1. QMA, 即 NP 的 quantum analog: {\sf QMA} \subseteq {\sf P}^{\sf ||QMA}={\sf P}^{\sf QMA[log]} \subseteq {\sf P}^{\sf QMA}

考虑这么一个问题, 假设有一个多项式个量子比特的量子态 |\psi\rangle , 不过你只能拿到从这个态得到的若干个约化密度矩阵 (local density matrices), 能不能判断这些约化密度矩阵都是来自这个量子态 |\psi\rangle 的呢? 这个问题的 QMA-hardness 证明最早 (2006 年) 用的是 Cook reduction [1], 直到两个月前大家终于搞清楚了怎么用 Karp reduction 证明 [2] -- 这样做还有一些额外的好处, 譬如说比较自然地写出关于 QMA 的 Sigma protocol (即一类使用 bit committment 的 著名的零知识证明协议).

此外, 如果我们按照上述三种 oracle 查询方式定义 QMA 的变种的话, 那么 {\sf QMA} \subseteq {\sf P}^{\sf ||QMA}={\sf P}^{\sf QMA[\log]} \subseteq {\sf P}^{\sf QMA}, 也就是说和 NP 类似. 假设 QMA 不对补封闭的话, 我们可以得到类似的结果 [3], 即 {\sf P}^{\sf QMA[log]} 比 QMA 稍微大一点. 中间的等号的证明也是很近的结果, 见 [4].

2. PP, 即 NP 的计数 (判定) 版本: {\sf PP}={\sf P}^{\sf ||PP} \subseteq {\sf P}^{\sf PP}={\sf P}^{\sf \#P}

NP 的非确定性图灵机定义告诉我们, 如果一个问题在 NP 里, 那么我们可以找到一个解. 如果我们想数到底有多少个解的话, 那么对应的复杂性类是 #P. 如果我们想知道解的个数是大于还是小于某个确定的数 (比如所有计算分支的数量的一半的话), 那么对应的复杂性类是 PP.

如果我们对 PP 考虑上面三种 oracle 查询方式的话, 那么 {\sf PP}={\sf P}^{\sf ||PP} \subseteq {\sf P}^{\sf PP}={\sf P}^{\sf \#P}. 也就是说 PP 对 truth-table reduction 封闭; 而另一方面, 尽管 #P 看起来是个比 PP 大一点的复杂性类, 但每个对 #P oracle 的查询都可以用多项式次 PP oracle 的 adaptive query 来模拟 (做二分查找).

3. PSPACE, 多项式空间: {\sf PSPACE}={\sf P}^{{\sf ||PSPACE}}={\sf P}^{{\sf PSPACE}}

我们同样可以定义 PSPACE 在上述三种 oracle 查询方式下的复杂性类, 但我们会得到 {\sf PSPACE}={\sf P}^{{\sf ||PSPACE}}={\sf P}^{{\sf PSPACE}}. 事实上, 可以证明 {\sf PSPACE}^{\sf PSPACE}={\sf PSPACE}, 也就是说 PSPACE 不但对上述三种规约方式封闭, 甚至即使允许多项式空间规约仍然是封闭的.

参考文献

[0] 需要说明的是, 这一提法对于 Karp reduction 并不完全准确, 因为它对某个语言和它的补很敏感: 如果 x\in\mathcal{L} , 那么作用规约 f 后的 f(x) \in \mathcal{L'}; 如果 x\in\overline{\mathcal{L}} , 那么 f(x) \in \overline{\mathcal{L}'}. 当然, 如果我们只关心 P-vs-NP 的话, 这样的限制是多余的. 如此定义排除了下述情况: 考虑 \mathcal{L}=\mathrm{SAT} 但 \mathcal{L}'=\overline{\mathrm{SAT}}, 即 \mathsf{coNP} \subseteq \mathsf{P}^{\mathsf{NP[1]}} 并不能推出 \overline{\mathrm{SAT}} 能通过 Karp reduction 到 \mathrm{SAT}. 类似的例子还有停机问题 (Halting).

[1] Consistency of Local Density Matrices is QMA-complete

[2] Zero-Knowledge for QMA from Locally Simulatable Proofs

[3] On physical problems that are slightly more difficult than QMA

[4] Oracle complexity classes and local measurements on physical Hamiltonians

这是比较专业的问题，建议去看wiki或者论文吧。归约的种类太多了。A到B的归约本质就是调用某个问题即函数B解函数A的算法。

图灵归约是我知道的要求最低的归约，其次是tt （truth table）归约，（限制为k个问题的k-tt归约比tt更强一点），最强的是多一归约（many one）。