复杂类

1. 前置

• Turing-machine

2. 复杂类

计算复杂性理论按照计算问题所需的资源（例如时间和空间）对问题进行分类。下面以二进制编码的语言 $L\subseteq \{0,1{\}}^{\ast }$ 为基础，定义 P、NP 和 #P。

2.1. P（Polynomial Time）

P 是可由确定性图灵机在多项式时间内判定的语言类。形式地，若存在一个确定性图灵机 $M$ 和常数 $k\ge 1$，使得对任意输入 $x\in \{0,1{\}}^{\ast }$：

1. $M$ 在 $O(|x{|}^k)$ 步内停机；
2. $M$ 接受 $x$ 当且仅当 $x\in L$，

则称 $L\in \mathrm{P}$。等价地，

$$\mathrm{P}=\bigcup _{k\ge 1}\mathrm{DTIME}(n^k).$$

这里的“判定”要求机器对每个输入都停机，并给出“接受”或“拒绝”的答案。

2.2. NP（Nondeterministic Polynomial Time）

NP 有两种常用且等价的定义。

2.2.1. 非确定性图灵机定义

若存在一个非确定性图灵机 $N$ 和常数 $k\ge 1$，使得：

1. $N$ 在输入 $x$ 上的每条计算分支都在 $O(|x{|}^k)$ 步内停机；
2. $x\in L$ 当且仅当至少存在一条接受分支，

则称 $L\in \mathrm{NP}$。等价地，

$$\mathrm{NP}=\bigcup _{k\ge 1}\mathrm{NTIME}(n^k).$$

这里的非确定性机器并不是依次遍历整棵计算树；“存在接受分支”是对所有可能计算分支的数学描述。

2.2.2. 多项式时间验证机定义

若存在一个多项式 $p$ 和一个确定性多项式时间验证机 $V$，使得对任意 $x\in \{0,1{\}}^{\ast }$，

$$x\in L⟺\exists y\in \{0,1{\}}^{\ast }(|y|\le p(|x|)\wedge V(x,y)=1),$$

则称 $L\in \mathrm{NP}$。字符串 $y$ 称为 $x$ 的证书（certificate）或见证（witness）。

这一定义表达的是：属于语言的实例拥有长度为多项式、并且可以在多项式时间内验证的证明。显然，

$$\mathrm{P}\subseteq \mathrm{NP},$$

但目前尚不知道该包含关系是否严格，即 $\mathrm{P}\stackrel{?}{=}\mathrm{NP}$ 仍是开放问题。

2.3. p（Sharp-P）

与 P 和 NP 不同，#P 是函数复杂度类，而不是语言（判定问题）复杂度类。一个函数

$$f:\{0,1{\}}^{\ast }\to \mathbb{N}$$

属于 $\#\mathrm{P}$，当且仅当存在一个多项式 $p$ 和一个确定性多项式时间谓词 $V$，使得对每个输入 $x$，

$$f(x)=\left|\left\{y\in \{0,1{\}}^{p(|x|)}|V(x,y)=1\right\}\right|.$$

等价地，$f(x)$ 是某台多项式时间非确定性图灵机在输入 $x$ 上的接受计算分支数。

2.4. NP 与 p 的联系

对固定的验证机 $V$ 和证书长度多项式 $p$，定义

$$f_V(x)=\left|\left\{y\in \{0,1{\}}^{p(|x|)}|V(x,y)=1\right\}\right|.$$

则

$$x\in L⟺f_V(x)>0.$$

因此，NP 只询问合法证书是否存在，而 p 计算合法证书的总数。典型的 p 问题包括计算布尔公式的满足赋值数（#SAT）和计算图的完美匹配数。