Other - 计算理论基础 - 《算法竞赛模板库》

问题
图灵机
可计算性
- 不可计算问题
- 停机问题
丘奇 - 图灵论题
复杂度类
多项式时间
可构造函数
- 时间可构造函数
- 空间可构造函数
复杂度类之间的关系
参考资料

copy from https://oi-wiki.org/misc/cc-basic/

本部分将介绍基础的计算理论的知识。这部分内容在 OI 中作用不大（但还是略有作用：如果你遇到了一个 NP-hard 问题，你可以认为它是不存在多项式复杂度的解法的），可以作为兴趣了解，或者为以后的学习做准备。

本文中许多结论都是不加证明的，如果有兴趣的话可以自行查阅相关证明。

前置知识：时间复杂度。

问题

语言

一个 字母表（alphabet) 是一个非空有限集合，该集合中的元素称为 符号/字符（symbol)。

令 $计算理论基础 - 图1$ 表示非负整数个 $计算理论基础 - 图2$ 中的字符连接而成的串，字母表 $计算理论基础 - 图3$ 上的一个 语言（language) 是 $计算理论基础 - 图4$ 的一个子集。

需要注意的是，这里的“语言”是一个抽象的概念，通常意义上的字符串是语言，所有的有向无环图也可以是一个语言（01 串与有向图之间可以建立双射，具体方式无需了解）。

由于任何语言都可以转化成 01 串的形式，所以在下文中不加说明时 $计算理论基础 - 图5$ 。

判定问题

判定问题就是只能用 YES/NO 回答的问题，本质上是判定一个串是否属于一个语言，即： $计算理论基础 - 图6$ %3D1%5Ciff%20x%5Cin%20L#card=math&code=f%3A%5CSigma%5E%5Cast%5Crightarrow%5C%7B0%2C%201%5C%7D%2C%20f%28x%29%3D1%5Ciff%20x%5Cin%20L&id=YKGcP) 是一个关于字母表 $计算理论基础 - 图7$ 和语言 $计算理论基础 - 图8$ 的判定问题。如，“判定一张图是不是一个有向无环图”就是一个判定问题。

判定问题由于其简洁性而常常被作为计算理论研究的对象。本文中不加说明时，“问题”都指“判定问题”，当然，有时一些命题也能简单地推广到其它问题上。

一个语言也可以代指“判定一个串是否属于这个语言”这个判定问题，因此，“语言”和“问题”可以视作同义词。

功能性问题

功能性问题的回答不止 YES/NO，可以是一个数或是其它。如，“求两个数的和”就是一个功能性问题。

任何功能性问题都可以转化为一个判定问题，如，“求两个数的和”可以转化为“判定两个数的和是否等于第三个数”。

判定问题也可以转化为一个功能性问题：求这个判定问题的指示函数，即上文中判定问题定义里的 $计算理论基础 - 图9$ 。

图灵机

确定性图灵机

不加说明时，“图灵机”往往指“确定性图灵机”，本文中也是如此。

图灵机有很多不同的定义，这里选取其中一种，其它定义下的图灵机往往与下面这种定义的图灵机计算能力等价。

图灵机是一个在一条可双向无限延伸且被划分为若干格子的纸带上进行操作的机器，其有内部状态，还有一个可以在纸带上进行修改与移动的磁针。

正式地说，图灵机是一个七元组 $计算理论基础 - 图10$ ，其中：

$计算理论基础 - 图11$ 是一个有限非空的 状态集合；
$计算理论基础 - 图12$ 是一个有限非空的 磁带字母表；
$计算理论基础 - 图13$ 是 空字符，它是唯一一个在计算过程中可以在磁带上无限频繁地出现的字符；
$计算理论基础 - 图14$ #card=math&code=%5CSigma%5Csubseteq%28%5CGamma%5Csetminus%5C%7Bb%5C%7D%29&id=eGTN0) 是 输入符号集，是可以出现在初始磁带（即输入）上的字符；
$计算理论基础 - 图15$ 是 初始状态；
$计算理论基础 - 图16$ 是 接受状态，如果一个图灵机在某个接受状态停机，则称初始磁带上的内容被这个图灵机接受。
$计算理论基础 - 图17$ %5Ctimes%20%5CGamma%20%5Cnot%20%5Cto%20Q%5Ctimes%20%5CGamma%20%5Ctimes%20%5C%7BL%2CR%5C%7D#card=math&code=%5Cdelta%20%3A%28Q%5Csetminus%20F%29%5Ctimes%20%5CGamma%20%5Cnot%20%5Cto%20Q%5Ctimes%20%5CGamma%20%5Ctimes%20%5C%7BL%2CR%5C%7D&id=ajE1f) 是一个被称作 转移函数 的 partial function（即只对定义域的一个子集有定义的函数）。如果 $计算理论基础 - 图18$ 在当前状态下没有定义，则图灵机停机。

图灵机从初始状态与纸带起点起，每次根据当前的内部状态 $计算理论基础 - 图19$ 和当前磁针指向的纸带上的单元格中的字符 $计算理论基础 - 图20$ 进行操作：若 $计算理论基础 - 图21$ #card=math&code=%5Cdelta%28x%2C%20y%29&id=ZSQX0) 没有定义则停机，否则若 $计算理论基础 - 图22$ %3D(a%2C%20b%2C%20c)#card=math&code=%5Cdelta%28x%2C%20y%29%3D%28a%2C%20b%2C%20c%29&id=lPDc5)，则将内部状态修改为 $计算理论基础 - 图23$ ，将磁针指向的格子中的字符修改为 $计算理论基础 - 图24$ ，若 $计算理论基础 - 图25$ 为 $计算理论基础 - 图26$ 则向左移动一格，为 $计算理论基础 - 图27$ 则向右移动一格。

其实，知道图灵机的工作细节是不必要的，只需建立直观理解即可。

图灵机 $计算理论基础 - 图28$ 在输入 $计算理论基础 - 图29$ 下的输出记作 $计算理论基础 - 图30$ #card=math&code=M%28x%29&id=uDMZ7)（ $计算理论基础 - 图31$ %3D1#card=math&code=M%28x%29%3D1&id=nofoH) 当且仅当 $计算理论基础 - 图32$ 接受 $计算理论基础 - 图33$ ， $计算理论基础 - 图34$ %3D0#card=math&code=M%28x%29%3D0&id=I920h) 当且仅当 $计算理论基础 - 图35$ 在输入 $计算理论基础 - 图36$ 下在有限步骤内停机且 $计算理论基础 - 图37$ 不接受 $计算理论基础 - 图38$ ），也可以在括号内包含多个参数，用逗号隔开，具体实现时可以向字母表中添加一个元素表示逗号来隔开各个参数。

图灵机与冯·诺依曼计算机解决问题的时间复杂度差别在多项式级别内，所以研究复杂度类时可以使用图灵机作为计算模型。

非确定性图灵机

非确定型图灵机是图灵机的一种，它与确定型图灵机的不同在于：确定型图灵机的每一步只能转移到一个状态，而非确定型图灵机可以“同时”转移到多个状态，从而在多个“分支”并行计算，一旦这些“分支”中有一个在接受状态停机，则此非确定性图灵机接受这个输入。

事实上，任何确定型图灵机都可以用类似于迭代加深搜索的方式在指数级时间内模拟一台非确定型图灵机多项式时间内的行为。

在现实生活中，确定型图灵机相当于单核处理器，只支持串行处理；而非确定型图灵机相当于理想的多核处理器，支持无限大小的并行处理。

多带图灵机

标准的图灵机只能在一条纸带上进行操作，但为了方便，本文中研究多带图灵机。对于一个 $计算理论基础 - 图39$ 带图灵机，其中一条纸带是只读的输入带，而剩下的 $计算理论基础 - 图40$ 条纸带可以进行读写，并且这 $计算理论基础 - 图41$ 条纸带中还有一条纸带用作输出。

多带图灵机的纸带数必须是有限的。

对于一个多带图灵机，它使用的空间是磁头在除输入带外的其它纸带上所访问过的单元格数目。

图灵机的编码

图灵机可以被自然数编码，即存在满射函数 $计算理论基础 - 图42$ ，使得每个自然数都对应一个图灵机，而每个图灵机都有无数个编码。因此，由若干图灵机构成的集合可以是一个语言。

记由自然数 $计算理论基础 - 图43$ 编码的图灵机为 $计算理论基础 - 图44$ 。

通用图灵机

存在一台图灵机 $计算理论基础 - 图45$ 满足：

若 $计算理论基础 - 图46$ 在输入 $计算理论基础 - 图47$ 下在有限时间内停机，则 $计算理论基础 - 图48$ %3DM%7B%5Calpha%7D(x)#card=math&code=%5Cmathcal%7BU%7D%28x%2C%20%5Calpha%29%3DM%7B%5Calpha%7D%28x%29&id=UMxZh)，否则 $计算理论基础 - 图49$ #card=math&code=%5Cmathcal%7BU%7D%28x%2C%20%5Calpha%29&id=T9MS7) 不会在有限时间内停机；
如果对于任意 $计算理论基础 - 图50$ ， $计算理论基础 - 图51$ 在输入 $计算理论基础 - 图52$ 下在 $计算理论基础 - 图53$ #card=math&code=T%28%7Cx%7C%29&id=sseLm) 时间内停机，则对于任意 $计算理论基础 - 图54$ ， $计算理论基础 - 图55$ #card=math&code=%5Cmathcal%7BU%7D%28x%2C%20%5Calpha%29&id=BQ53g) 在 $计算理论基础 - 图56$ %5Clog%20T(%7Cx%7C))#card=math&code=O%28T%28%7Cx%7C%29%5Clog%20T%28%7Cx%7C%29%29&id=MNfk4) 时间内停机。

即：存在一台通用图灵机，它能模拟任何一台图灵机，且花费的时间只会比这台被模拟的图灵机慢其运行时间的对数。

可计算性

不可计算问题

对于一个判定问题，若存在一个总是在有限步内停机且能够正确进行判定的图灵机，则这个问题是一个 图灵可计算 的问题，否则这个问题是一个 图灵不可计算 的问题。

由于图灵机可以被自然数编码，所以图灵机的个数是可数无穷，而语言（即二进制串的集合）的个数是不可数无穷，而每个图灵机最多判定一个语言，所以一定存在图灵不可计算的问题。

停机问题

停机问题是一个经典的图灵不可计算问题：给定 $计算理论基础 - 图57$ 和 $计算理论基础 - 图58$ ，判定 $计算理论基础 - 图59$ 在输入为 $计算理论基础 - 图60$ 时是否会在有限步内停机。

??? note “停机问题是图灵不可计算的证明”
定义函数 $计算理论基础 - 图61$ 为：

$$
\mathsf{UC}(\alpha)=\begin{cases}0&M_\alpha(\alpha)=1\\1&\text{otherwise}\end{cases}
$$
我们先证明 $\mathsf{UC}$ 函数是图灵不可计算的：
假设存在一台图灵机 $M_{\beta}$ 能够计算 $\mathsf{UC}$，那么根据 $\mathsf{UC}$ 的定义可以得到 $\mathsf{UC}(\beta)=1\iff M_\beta(\beta)\neq 1$，而根据 $M_{\beta}$ 能够计算 $\mathsf{UC}$ 可以得到 $M_{\beta}(\beta)=\mathsf{UC}(\beta)$，产生了矛盾，所以假设不成立，不存在可以计算 $\mathsf{UC}$ 的图灵机。
令 $M_{\mathsf{HALT}}$ 是一个可以解决停机问题的图灵机，$M_{\mathsf{HALT}}(x,\alpha)$ 的值是判定问题 $M_\alpha$ 在输入为 $x$ 时是否会在有限步内停机的解，那么我们可以构造出一台能够计算 $\mathsf{UC}$ 函数的图灵机 $M_{\mathsf{UC}}$：
$M_\mathsf{UC}$ 首先调用 $M_\mathsf{HALT}(α,α)$, 如果它输出 $0$, 则 $M_\mathsf{UC}(α)=1$；否则，$M_\mathsf{UC}$ 使用通用图灵机模拟计算得到答案。
由于 $\mathsf{UC}$ 函数是图灵不可计算的，所以 $M_\mathsf{HALT}$ 不存在，也就是说停机问题是图灵不可计算的。

丘奇 - 图灵论题

丘奇 - 图灵论题称，若一类问题有一个有效的方法解决，则这类问题可以被某个图灵机解决。

其中，“有效的方法”需要满足：

包含有限条清晰的指令；
当用其解决这类问题的其中一个时，这个方法需要在有限步骤内结束，且得到正确的答案。

这个论题没有被证明，但其是计算理论的一条基本公理。

复杂度类

复杂度类有很多，本文只会介绍其中较为常见的一小部分。

R 和 RE

对于语言 $计算理论基础 - 图62$ 和图灵机 $计算理论基础 - 图63$ ，若 $计算理论基础 - 图64$ 在任何输入下都能在有限步骤内停机，且 $计算理论基础 - 图65$ %3D1%5Ciff%20x%5Cin%20L#card=math&code=M%28x%29%3D1%5Ciff%20x%5Cin%20L&id=TkiiQ)，则称 $计算理论基础 - 图66$ 能够判定 $计算理论基础 - 图67$ 。

对于语言 $计算理论基础 - 图68$ 和图灵机 $计算理论基础 - 图69$ ，若对于任何属于 $计算理论基础 - 图70$ 的输入， $计算理论基础 - 图71$ 都在有限步骤内停机，且 $计算理论基础 - 图72$ %3D1%5Ciff%20x%5Cin%20L#card=math&code=M%28x%29%3D1%5Ciff%20x%5Cin%20L&id=fBTF7)，则称 $计算理论基础 - 图73$ 能够识别 $计算理论基础 - 图74$ 。

复杂度类 $计算理论基础 - 图75$ 表示那些可以被某台图灵机判定的语言的集合，即所有图灵可计算的语言。

复杂度类 $计算理论基础 - 图76$ 表示那些可以被某台图灵机识别的语言的集合。 $计算理论基础 - 图77$ 也被称作递归可枚举语言。

由定义可以得到 $计算理论基础 - 图78$ 。

DTIME

如果存在一台确定性图灵机能够判定一个语言，且对于任何输入 $计算理论基础 - 图79$ ，这台图灵机可以在 $计算理论基础 - 图80$ )#card=math&code=O%28f%28%7Cx%7C%29%29&id=XZKyd) 的时间内停机，那么这个语言属于 $计算理论基础 - 图81$ )#card=math&code=%5Cmathsf%7BDTIME%7D%28f%28n%29%29&id=gSil3) 类。

P

复杂度类 $计算理论基础 - 图82$ 表示可以由确定性图灵机在多项式时间内解决的判定问题，即：

$计算理论基础 - 图83$ %0A#card=math&code=%5Cmathsf%7BP%7D%3D%5Cbigcup%5Climits_%7Bk%5Cin%5Cmathbb%7BN%7D%7D%5Cmathsf%7BDTIME%7D%28n%5Ek%29%0A&id=eeCRq)

线性规划、计算最大公约数、求图的最大匹配的判定版本都是 $计算理论基础 - 图84$ 类问题。

EXPTIME

复杂度类 $计算理论基础 - 图85$ 表示可以由确定性图灵机在指数级时间内解决的判定问题，即：

$计算理论基础 - 图86$ %0A#card=math&code=%5Cmathsf%7BEXPTIME%7D%3D%5Cbigcup%5Climits_%7Bk%5Cin%5Cmathbb%7BN%7D%7D%5Cmathsf%7BDTIME%7D%282%5E%7Bn%5Ek%7D%29%0A&id=MVshM)

停机问题的弱化版——给定一个图灵机的编码以及一个正整数 $计算理论基础 - 图87$ ，判定这个图灵机是否在 $计算理论基础 - 图88$ 步内停机，是一个 $计算理论基础 - 图89$ 类的问题。因为这个问题的解法需要 $计算理论基础 - 图90$ #card=math&code=O%28k%29&id=TWnGl) 的时间，而数字 $计算理论基础 - 图91$ 可以被编码为长度为 $计算理论基础 - 图92$ #card=math&code=O%28%5Clog%20k%29&id=Lhj3n) 的二进制串。

NTIME

如果存在一台非确定性图灵机能够判定一个语言，且对于任何输入 $计算理论基础 - 图93$ ，这台图灵机可以在 $计算理论基础 - 图94$ )#card=math&code=O%28f%28%7Cx%7C%29%29&id=KaWGx) 的时间内停机，那么这个语言属于 $计算理论基础 - 图95$ )#card=math&code=%5Cmathsf%7BNTIME%7D%28f%28n%29%29&id=vyvZA) 类。

NP

复杂度类 $计算理论基础 - 图96$ 表示可以由非确定性图灵机在多项式时间内解决的判定问题，即：

$计算理论基础 - 图97$ %0A#card=math&code=%5Cmathsf%7BNP%7D%3D%5Cbigcup%5Climits_%7Bk%5Cin%5Cmathbb%7BN%7D%7D%5Cmathsf%7BNTIME%7D%28n%5Ek%29%0A&id=bIo84)

所有 $计算理论基础 - 图98$ 类问题都是 $计算理论基础 - 图99$ 类问题。更多 $计算理论基础 - 图100$ 类问题请参见下文中的 NPC 问题以及 NP-intermediate 问题。

NP-hard

如果所有 $计算理论基础 - 图101$ 类问题都可以在多项式时间内规约到问题 $计算理论基础 - 图102$ ，那么问题 $计算理论基础 - 图103$ 是 NP-hard 的。

换句话说，如果可以在一单位的时间内解决 NP-hard 的问题 $计算理论基础 - 图104$ ，那么所有 $计算理论基础 - 图105$ 类问题都可以在多项式单位的时间内解决。

NP-complete

如果一个问题既是 $计算理论基础 - 图106$ 类问题又是 NP-hard 的，那么这个问题是 NP 完全 (NP-complete) 的，或者说这是一个 NPC 问题。

一些经典的 NPC 问题：旅行商问题的判定版本、最大独立集问题的判定版本、最小点覆盖问题的判定版本、最长路问题的判定版本、0-1 整数规划问题的判定版本、集合覆盖问题、图着色问题、背包问题、三维匹配问题、最大割问题的判定版本。

NPC 问题的功能性版本往往是 NP-hard 的，例如：“判定一张图中是否存在大小为 $计算理论基础 - 图107$ 的团”既是一个 $计算理论基础 - 图108$ 类问题又是 NP-hard 的，从而它是一个 NPC 问题，而它的功能性版本“求一张图的最大团”不是 NPC 问题，但这个功能性版本依然是 NP-hard 的。

类似地，其它复杂度类也会有“XX-complete”，如所有 $计算理论基础 - 图109$ 类的问题都能在多项式时间内规约到 EXPTIME-complete 的问题。

co-NP

一个问题是 $计算理论基础 - 图110$ 类问题，当且仅当它的补集是 $计算理论基础 - 图111$ 类问题。如果将“问题”理解为“语言”，而“语言”是 $计算理论基础 - 图112$ 的子集，就能理解“补集”了。

例如：“给定 $计算理论基础 - 图113$ 个子集，判断是否能够从中选取 $计算理论基础 - 图114$ 个，覆盖整个集合”是一个 NPC 问题，而其补集“给定 $计算理论基础 - 图115$ 个子集，判断是否从中任取 $计算理论基础 - 图116$ 个都不能覆盖整个集合”是一个 $计算理论基础 - 图117$ 类问题。如果第一个问题的答案是“是”，那么相当于找到了第二个问题的一组反例，从而第二个问题的答案是“否”。

NP-intermediate

如果一个问题是 $计算理论基础 - 图118$ 类问题，但它既不是 $计算理论基础 - 图119$ 类问题也不是 NPC 问题，则称其为 NP-intermediate 问题。

就人们目前的了解，图同构问题、离散对数问题和因数分解问题可能是 NP-intermediate 的。

Ladner 定理指出，如果 $计算理论基础 - 图120$ ，则一定存在问题是 NP-intermediate 的。

NEXPTIME

复杂度类 $计算理论基础 - 图121$ 表示可以由非确定性图灵机在指数级时间内解决的判定问题，即：

$计算理论基础 - 图122$ %0A#card=math&code=%5Cmathsf%7BNEXPTIME%7D%3D%5Cbigcup%5Climits_%7Bk%5Cin%5Cmathbb%7BN%7D%7D%5Cmathsf%7BNTIME%7D%282%5E%7Bn%5Ek%7D%29%0A&id=GhG6K)

#P

$计算理论基础 - 图123$ 类问题不是判定问题，而是关于 $计算理论基础 - 图124$ 类问题的计数问题：数一个 $计算理论基础 - 图125$ 类问题的解的个数是一个 $计算理论基础 - 图126$ 类的问题。换句话说，数一个串在一个总是在多项式时间内停机的非确定性图灵机的多少个分支处被接受是一个 $计算理论基础 - 图127$ 类的问题。

求一张普通图或二分图的匹配或完美匹配个数都是 #P 完全的，对应的判定问题为“判定一张图是否存在（完美）匹配”。

DSPACE

如果存在一台确定性图灵机能够在输入为 $计算理论基础 - 图128$ 时在 $计算理论基础 - 图129$ )#card=math&code=O%28f%28%7Cx%7C%29%29&id=SnF5l) 的空间内判定一个语言，那么这个语言属于 $计算理论基础 - 图130$ )#card=math&code=%5Cmathsf%7BDSPACE%7D%28f%28n%29%29&id=p4nNO) 类。

$计算理论基础 - 图131$ )#card=math&code=%5Cmathsf%7BREG%7D%3D%5Cmathsf%7BDSPACE%7D%28O%281%29%29&id=hIRZC)，即正则语言，也就是自动机能够判定的语言。
$计算理论基础 - 图132$ )#card=math&code=%5Cmathsf%7BL%7D%3D%5Cmathsf%7BDSPACE%7D%28O%28%5Clog%20n%29%29&id=aHj2i)，需要注意的是图灵机使用的空间不包括输入占用的空间。
$计算理论基础 - 图133$ #card=math&code=%5Cmathsf%7BPSPACE%7D%3D%5Cbigcup%5Climits_%7Bk%5Cin%5Cmathbb%20N%7D%5Cmathsf%7BDSPACE%7D%28n%5Ek%29&id=SAxHM)
$计算理论基础 - 图134$ #card=math&code=%5Cmathsf%7BEXPSPACE%7D%3D%5Cbigcup%5Climits_%7Bk%5Cin%5Cmathbb%20N%7D%5Cmathsf%7BDSPACE%7D%282%5E%7Bn%5Ek%7D%29&id=OjyDN)

NSPACE

如果存在一台非确定性图灵机能够在输入为 $计算理论基础 - 图135$ 时在 $计算理论基础 - 图136$ )#card=math&code=O%28f%28%7Cx%7C%29%29&id=CjheK) 的空间内判定一个语言，那么这个语言属于 $计算理论基础 - 图137$ )#card=math&code=%5Cmathsf%7BNSPACE%7D%28f%28n%29%29&id=PpjNL) 类。

$计算理论基础 - 图138$ )%3D%5Cmathsf%7BNSPACE%7D(O(1))#card=math&code=%5Cmathsf%7BREG%7D%3D%5Cmathsf%7BDSPACE%7D%28O%281%29%29%3D%5Cmathsf%7BNSPACE%7D%28O%281%29%29&id=bjpbN)
$计算理论基础 - 图139$ )#card=math&code=%5Cmathsf%7BNL%7D%3D%5Cmathsf%7BNSPACE%7D%28O%28%5Clog%20n%29%29&id=QXi3o)
$计算理论基础 - 图140$ )#card=math&code=%5Cmathsf%7BCSL%7D%3D%5Cmathsf%7BNSPACE%7D%28O%28n%29%29&id=sfq7m)，即上下文相关语言。
$计算理论基础 - 图141$ #card=math&code=%5Cmathsf%7BPSPACE%7D%3D%5Cmathsf%7BNPSPACE%7D%3D%5Cbigcup%5Climits_%7Bk%5Cin%5Cmathbb%20N%7D%5Cmathsf%7BNSPACE%7D%28n%5Ek%29&id=nFbuG)
$计算理论基础 - 图142$ #card=math&code=%5Cmathsf%7BEXPSPACE%7D%3D%5Cmathsf%7BNEXPSPACE%7D%3D%5Cbigcup%5Climits_%7Bk%5Cin%5Cmathbb%20N%7D%5Cmathsf%7BNSPACE%7D%282%5E%7Bn%5Ek%7D%29&id=wKrSO)

多项式时间

简单来说，如果存在正数 $计算理论基础 - 图143$ 使得一个算法的时间复杂度为 $计算理论基础 - 图144$ #card=math&code=O%28n%5Ek%29&id=mGfjZ)（注意，不是 $计算理论基础 - 图145$ #card=math&code=%5CTheta%28n%5Ek%29&id=VhuWO)），其中 $计算理论基础 - 图146$ 为问题规模（输入的长度），则称这个算法是 多项式时间 的。如果一个问题有（确定性图灵机上的）多项式时间的算法来解决，则这个问题属于复杂度类 $计算理论基础 - 图147$ 。

多项式时间可分为强多项式时间和弱多项式时间，除此之外还有伪多项式时间。

Strongly polynomial time 强多项式时间

我们先定义一个计算模型，称作算术模型。在算术模型中，数字之间的算术运算（加减乘除、比较大小）可以在单位时间内完成（即 $计算理论基础 - 图148$ #card=math&code=O%281%29&id=rUQ4B) 时间内完成，与数字大小无关）。

如果一个算法在算术模型下的操作数是输入中的数字个数的多项式，并且空间复杂度是输入规模（而非数字个数）的多项式，则这个算法是 强多项式时间 的。由于算术操作在一般的计算模型下可以在输入规模（即数字大小的对数）的多项式时间内完成，强多项式时间的算法一定是多项式时间的。

一般来说，强多项式时间的算法的时间复杂度与值域无关。

Weakly polynomial time 弱多项式时间

如果一个算法是多项式时间的但不是强多项式时间的，则它是 弱多项式时间 的。

例如，计算最大公约数的欧几里得算法，时间复杂度为 $计算理论基础 - 图149$ #card=math&code=O%28%5Clog%20a%20%2B%20%5Clog%20b%29&id=Henbb)（ $计算理论基础 - 图150$ 和 $计算理论基础 - 图151$ 为输入的数的大小），是弱多项式时间的。

Pseudo-polynomial time 伪多项式时间

如果一个算法的用时是值域的多项式，则称它是 伪多项式时间 的。伪多项式时间的算法可能是多项式时间的也可能不是，可能不是多项式时间是因为表示一个大小为 $计算理论基础 - 图152$ 的正整数一般只需要 $计算理论基础 - 图153$ #card=math&code=O%28%5Clog%20n%29&id=vRdMM) 个二进制位，所以关于值域多项式时间的算法往往关于输入长度是指数级时间的。虽然从定义上来说伪多项式时间也可能是多项式时间，但当我们说一个算法是伪多项式时间的，一般都是说这个算法不是多项式时间的。

例如，背包问题是 NP-hard 问题，但它有基于动态规划的伪多项式时间的解法。

如果一个 NPC/NP-hard 问题有伪多项式时间的解法，则称这个问题是 弱 NPC/弱 NP-hard 问题。如果一个 NPC/NP-hard 问题在 $计算理论基础 - 图154$ 的前提下没有伪多项式时间的解法，则称这个问题是 强 NPC/强 NP-hard 问题。

可构造函数

时间可构造函数

有时，我们想让图灵机知道自己用了多长的时间，例如，强制图灵机在进行 $计算理论基础 - 图155$ #card=math&code=T%28n%29&id=m5e0E) 步计算后停机。但如果计算 $计算理论基础 - 图156$ #card=math&code=T%28n%29&id=QqFTO) 的用时就超过了 $计算理论基础 - 图157$ #card=math&code=T%28n%29&id=Lkd0h)，这便是不可做到的。为此，定义了时间可构造函数，来避免这样的麻烦。

如果存在图灵机 $计算理论基础 - 图158$ ，使得输入为 $计算理论基础 - 图159$ ( $计算理论基础 - 图160$ 个 1) 时 $计算理论基础 - 图161$ 能在 $计算理论基础 - 图162$ )#card=math&code=O%28f%28n%29%29&id=oeMuH) 的时间内停机并且输出 $计算理论基础 - 图163$ #card=math&code=f%28n%29&id=sbeEl) 的二进制表示（注意，这里的图灵机的输出不是接受/不接受，而是一个串，输出可以在纸带上进行），则 $计算理论基础 - 图164$ #card=math&code=f%28n%29&id=yvhLq) 是一个 时间可构造函数。

由于读入需要 $计算理论基础 - 图165$ #card=math&code=O%28n%29&id=pqpii) 的时间， $计算理论基础 - 图166$ #card=math&code=o%28n%29&id=czriV) 的非常值函数都不是时间可构造函数。

空间可构造函数

类似地可以定义空间可构造函数。

如果存在图灵机 $计算理论基础 - 图167$ ，使得输入为 $计算理论基础 - 图168$ ( $计算理论基础 - 图169$ 个 1) 时 $计算理论基础 - 图170$ 能在 $计算理论基础 - 图171$ )#card=math&code=O%28f%28n%29%29&id=KEXWA) 的空间内停机并且输出 $计算理论基础 - 图172$ #card=math&code=f%28n%29&id=vYATI) 的二进制表示，则 $计算理论基础 - 图173$ #card=math&code=f%28n%29&id=pbMoG) 是一个 空间可构造函数。

复杂度类之间的关系

时间谱系定理

确定性时间谱系定理

若 $计算理论基础 - 图174$ #card=math&code=f%28n%29&id=BTJrs) 是一个时间可构造函数，则：

$计算理论基础 - 图175$ %7D%7B%5Clog%20f(n)%7D%7D%5Cright)%5Cright)%5Csubsetneq%20%5Cmathsf%20%7BDTIME%7D(f(n))%0A#card=math&code=%5Cmathsf%20%7BDTIME%7D%5Cleft%28o%5Cleft%28%7B%5Cfrac%20%7Bf%28n%29%7D%7B%5Clog%20f%28n%29%7D%7D%5Cright%29%5Cright%29%5Csubsetneq%20%5Cmathsf%20%7BDTIME%7D%28f%28n%29%29%0A&id=HrAVC)

由确定性时间谱系定理可以得到 $计算理论基础 - 图176$ 。

??? note “确定性时间谱系定理的证明”
定义语言 $计算理论基础 - 图177$ %7C%5Cmathcal%7BU%7D((x%2C%20y)%2C%20x)%5Ctext%7B%20%E5%9C%A8%20%7Df(%7Cx%7C%2B%7Cy%7C)%5Ctext%7B%20%E6%97%B6%E9%97%B4%E5%86%85%E5%81%9C%E6%9C%BA%E5%B9%B6%E6%8B%92%E7%BB%9D%7D%5C%7D#card=math&code=L%3D%5C%7B%28x%2C%20y%29%7C%5Cmathcal%7BU%7D%28%28x%2C%20y%29%2C%20x%29%5Ctext%7B%20%E5%9C%A8%20%7Df%28%7Cx%7C%2B%7Cy%7C%29%5Ctext%7B%20%E6%97%B6%E9%97%B4%E5%86%85%E5%81%9C%E6%9C%BA%E5%B9%B6%E6%8B%92%E7%BB%9D%7D%5C%7D&id=AbFyw)，由于 $计算理论基础 - 图178$ #card=math&code=f%28n%29&id=v503f) 是一个时间可构造函数，可以根据定义进行计算来判定 $计算理论基础 - 图179$ ，用时为 $计算理论基础 - 图180$ )#card=math&code=O%28f%28%7Cx%7C%2B%7Cy%7C%29%29&id=ysPJb)，所以 $计算理论基础 - 图181$ )#card=math&code=L%5Cin%5Cmathsf%7BDTIME%7D%28f%28n%29%29&id=QD2pg)。

现在假设 $L\in\mathsf{DTIME}(o\left({\dfrac {f(n)}{\log f(n)}}\right))$，设 $M_z$ 就是那台在 $o\left({\dfrac {f(n)}{\log f(n)}}\right)$ 的时间内判定 $L$ 的图灵机。
令通用图灵机 $\mathcal{U}(x, z)$ 关于 $x$ 的用时为 $g(|x|)$，由上文关于通用图灵机的介绍可以得到 $g(n)=o(f(n))$，所以，当 $y$ 足够大时，$g(|z|+|y|)<f(|z|+|y|)$。
令 $y'$ 是一个足够大的 $y$，那么 $\mathcal{U}((z, y'), z)$ 一定能在 $f(|z|+|y'|)$ 时间内停机，从而 $M_z(z, y')\ne M_z(z, y')$，产生矛盾，所以假设不成立，确定性时间谱系定理证毕。

非确定性时间谱系定理

若 $计算理论基础 - 图182$ #card=math&code=g%28n%29&id=JQMdd) 是一个时间可构造函数，并且 $计算理论基础 - 图183$ %3Do(g(n))#card=math&code=f%28n%2B1%29%3Do%28g%28n%29%29&id=WnQSO)，则 $计算理论基础 - 图184$ )%5Csubsetneq%5Cmathsf%7BNTIME%7D(g(n))#card=math&code=%5Cmathsf%7BNTIME%7D%28f%28n%29%29%5Csubsetneq%5Cmathsf%7BNTIME%7D%28g%28n%29%29&id=NPrLe)。

由非确定性时间谱系定理可以得到 $计算理论基础 - 图185$ 。

空间谱系定理

若 $计算理论基础 - 图186$ #card=math&code=f%28n%29&id=Nz1L2) 是一个空间可构造函数且 $计算理论基础 - 图187$ %3D%5COmega(%5Clog%20n)#card=math&code=f%28n%29%3D%5COmega%28%5Clog%20n%29&id=ekgPQ)，则 $计算理论基础 - 图188$ ))%5Csubsetneq%5Cmathsf%7BSPACE%7D(f(n))#card=math&code=%5Cmathsf%7BSPACE%7D%28o%28f%28n%29%29%29%5Csubsetneq%5Cmathsf%7BSPACE%7D%28f%28n%29%29&id=zuzH9)。

其中 $计算理论基础 - 图189$ 可以代指 $计算理论基础 - 图190$ 或 $计算理论基础 - 图191$ 。

由空间谱系定理可以得到 $计算理论基础 - 图192$ 。

萨维奇定理

一台确定性图灵机可以在一台非确定性图灵机所消耗空间的平方内模拟它（尽管消耗的时间可能多很多），即：

若 $计算理论基础 - 图193$ %3D%5COmega(%5Clog%20n)#card=math&code=f%28n%29%3D%5COmega%28%5Clog%20n%29&id=m5lLu)，则：

$计算理论基础 - 图194$ %5Cright)%5Csubseteq%20%5Cmathsf%20%7BDSPACE%7D%5Cleft(%5Cleft(f%5Cleft(n%5Cright)%5Cright)%5E2%5Cright)%0A#card=math&code=%5Cmathsf%7BNSPACE%7D%5Cleft%28f%5Cleft%28n%5Cright%29%5Cright%29%5Csubseteq%20%5Cmathsf%20%7BDSPACE%7D%5Cleft%28%5Cleft%28f%5Cleft%28n%5Cright%29%5Cright%29%5E2%5Cright%29%0A&id=vEldh)

推论： $计算理论基础 - 图195$ ， $计算理论基础 - 图196$ 。

P?=NP

复杂度类 $计算理论基础 - 图197$ 与 $计算理论基础 - 图198$ 是否相等是计算复杂度理论中一个著名的尚未解决的问题。

若 $计算理论基础 - 图199$ ，可以得到 $计算理论基础 - 图200$ ，但反之不行（目前没有基于 $计算理论基础 - 图201$ 证明 $计算理论基础 - 图202$ 的方法）。

???+note “为什么 NP?=co-NP 不是显然的？”
由于 $计算理论基础 - 图203$ 问题和与其对应的 $计算理论基础 - 图204$ 问题答案相反，很容易有这种想法：对于一个 $计算理论基础 - 图205$ 问题，我只要将解决其补集的非确定性图灵机的输出反过来，就解决了该 $计算理论基础 - 图206$ 问题，所以 $计算理论基础 - 图207$ 。

实际上，上面所说的这种方法确实能够解决该 $\mathsf{co-NP}$ 问题，但并没有找到一个非确定性图灵机来解决它：如果一个图灵机所做的事情是将一个非确定性图灵机的输出反过来，该图灵机并不是一个非确定性图灵机。因为，非确定性图灵机接受是在某个分支处接受，而拒绝是在所有分支处拒绝；而将其输出反过来，就变成了接受是在所有分支处，而拒绝是在一个分支处，而这样就不符合非确定性图灵机的定义了，所以能用该图灵机解决这个 $\mathsf{co-NP}$ 问题并不能使这个 $\mathsf{co-NP}$ 问题变成一个 $\mathsf{NP}$ 问题。

若 $计算理论基础 - 图208$ ，还可以得到 $计算理论基础 - 图209$ 。

若 $计算理论基础 - 图210$ ，可以得到 NP-intermediate 不为空。

计算理论基础

问题

语言