第 11 章其他问题类

co-NP、PSPACE、随机化复杂度与素数性测试

Source scope
主要依据教材第 11 章：中文印刷页 329–357，对应 PDF p.342–370。目录明确讨论 NP 语言的补、PSPACE/NPSPACE、PSPACE 完全性与 QBF、随机化语言类 RP/ZPP，以及素数性测试的复杂性。

1 0. 为什么 NP 不是复杂度理论的终点

第 10 章集中于 \(P\)、\(NP\) 与 NP 完全性。但复杂度世界远不止这两类。本章展示三条扩展方向：

对 yes/no 互换后的复杂度：co-NP；
用“空间”而不是“时间”衡量资源：PSPACE；
允许随机选择：随机化复杂度类。

2 1. NP 中语言的补：co-NP

定义

\[ coNP=\{L\mid \overline L\in NP\}. \]

若 \(L\in P\)，则其补也在 \(P\)，所以

\[ P\subseteq NP\cap coNP. \]

一个典型对照：

SAT：存在一个满足赋值；证书容易给出；
UNSAT：要证明不存在任何满足赋值，证书结构不显然。

2.1 1.1 NP 完全问题与 co-NP

若某个 NP 完全语言同时属于 co-NP，则可推出整个 NP 被包含进 co-NP，进而得到

\[ NP=coNP. \]

一般认为这一等式并未被证明。

3 2. 多项式空间：PSPACE

若存在确定型 TM，在输入长度 \(n\) 上只使用多项式数量的工作带单元，即空间

\[ O(n^k), \]

则语言属于 PSPACE。

这里时间可以很长；只限制“同时占用多少存储”。

3.1 2.1 P 与 PSPACE

任何多项式时间算法至多访问多项式个带单元，因此

\[ P\subseteq PSPACE. \]

3.2 2.2 NPSPACE

NPSPACE 允许非确定型多项式空间。

教材讨论确定型与非确定型多项式空间之间的关系。经典结论是：非确定性在多项式空间层面不会带来额外语言能力，即

\[ PSPACE=NPSPACE. \]

4 3. PSPACE 完全问题与 QBF

4.1 3.1 量词布尔公式

QBF（Quantified Boolean Formula）在布尔公式前加入量词：

\[ \exists x_1\forall x_2\exists x_3\cdots\phi(x_1,x_2,x_3,\ldots). \]

求值规则与一场轮流选择变量的博弈类似：

\(\exists\) 玩家试图使公式为真；
\(\forall\) 玩家试图使公式为假。

4.2 3.2 QBF 为什么在 PSPACE

递归处理量词：

\(\exists x\,\psi\)：尝试 \(x=0\) 或 \(1\)，有一支真即可；
\(\forall x\,\psi\)：两种赋值都必须真。

深度最多是变量数。虽然分支数指数级，但深度优先计算只需保存当前赋值路径，因此空间是多项式。

4.3 3.3 PSPACE 完全性

QBF 是 PSPACE 完全问题。它在 PSPACE 中扮演的角色类似 SAT 在 NP 中的角色。

5 4. 随机化图灵机与 RP

随机化算法允许每一步获取随机位。分析结果不再只是“正确/错误”，还要讨论错误概率。

5.1 4.1 RP

一种常见定义：语言 \(L\in RP\)，若存在多项式时间随机算法满足：

若 \(x\notin L\)，永不错误接受；
若 \(x\in L\)，以至少某个常数概率（如 \(1/2\)）接受。

因此 RP 是单侧错误。

通过独立重复，yes-instance 的失败概率可指数下降。

6 5. ZPP

ZPP（zero-error probabilistic polynomial time）可以理解为：

永远不给错误答案；
期望运行时间为多项式。

教材讨论 RP 与 ZPP 的关系。常见关系写作

\[ ZPP=RP\cap coRP. \]

并有

\[ P\subseteq ZPP\subseteq RP\subseteq NP. \]

这些包含关系帮助理解随机化算法的位置。

7 6. 快速排序作为随机算法例子

随机化快速排序通过随机选 pivot 避免固定输入导致的持续最坏分割。

重要思想：

单次运行时间是随机变量；
我们分析期望复杂度；
随机性改变的是算法路径，不改变问题定义。

8 7. 素数性测试的复杂性

教材把素数性测试作为随机化计算的重要案例。

8.1 7.1 同余算术

若

\[ a\equiv b\pmod n, \]

表示 \(n\mid(a-b)\)。

模运算下可高效完成：

加法；
乘法；
快速幂。

快速模幂通过平方-乘算法在对数级乘法次数内计算

\[ a^k\bmod n. \]

8.2 7.2 随机素数性测试思想

很多合数存在大量可被随机抽中的“见证（witness）”。算法随机选择候选见证：

若找到违反某数论性质的见证，确定是合数；
若没有找到，只能以高概率相信可能是素数。

重复试验可降低错误概率。

8.3 7.3 非确定型视角

对合数，可以给出一个非平凡因子作为短证书；验证乘积与整除是多项式时间。这说明“合数性”天然具有 NP 证书。

教材还从复杂度类角度讨论素数性/合数性与随机化、非确定性之间的关系。

9 8. 各类之间的层次图

本章强调的是已知包含关系，而不是把未解决关系当成定理。

可安全记住：

\[ P\subseteq NP\subseteq PSPACE, \]

\[ P\subseteq coNP\subseteq PSPACE, \]

以及随机化类中的

\[ P\subseteq ZPP\subseteq RP\subseteq NP. \]

至于 \(P\) 是否等于 \(NP\)、\(NP\) 是否等于 \(coNP\) 等，均不能擅自画成严格包含或相等。

10 9. 常见错误

认为 co-NP 是“NP 的补集”；它是“补语言属于 NP 的语言类”；
把 PSPACE 理解成“程序文件大小”；它限制的是计算过程中使用的工作空间；
认为指数时间一定需要指数空间；深度优先搜索可能时间很长但空间较小；
混淆随机算法的单侧错误、双侧错误和零错误；
把概率正确说成绝对正确；
把尚未解决的复杂度类关系写成定理。

11 10. 全书收束

从第 2 章到第 11 章，课程形成了三层问题：

表达能力：什么模型能描述什么语言？
  Regular  ⊂  CFL  ⊂  Decidable  ⊂  Recognizable

可计算性：有没有算法？
  decidable / undecidable

复杂度：有算法以后，需要多少时间或空间？
  P, NP, coNP, PSPACE, randomized classes

这三层必须严格区分。