Does Many Mean More Than One? Computational Complexity

Turing Machines

图灵机(Turing machine)是以英国数学家艾伦图灵(Alan Turing)命名的一种理想化的计算机模型。它模拟一个算法，根据已有的规则，如何一步一步地从一个状态转移到另一个状态。一个图灵机 $T$ 包含以下四个部分。
(1) 磁带(Tape)。这是一个一维的单元格的数组，两端无限长。每一个单元格包含来自有限集合 $A$ 的一个符号，其中start,blank这两个是必须的。start是图灵机开始的地方，标识从哪里开始。磁带也称作机器的输入(input)。
(2) 磁头(head)。如果磁带包含很多信息，那么机器应该可以读它们。磁头可以沿着磁带向两端移动，读取单元格的符号，也可以写一个符号到当前单元格。磁头常常被称为读写(read-write)。
(3) 状态(state)集合 $S$ ，包含开始状态(start state) $s$ 。随着磁头沿着磁带读写，机器的状态进行转移。 $T$ 读到某个符号该如何进行状态变化依赖于当前的状态。换句话说， $t$ 状态读到 $a$ 和 $u$ 状态读到 $a$ 行为是不一样的。
(4) 转移函数(transition function)或程序(program)如下 $f:S\times A\to (S\cup\text{"Yes"}\cup\text{"No"}\times A\times\{\leftarrow,\rightarrow,\text{stay}\}$ 函数描述了 $T$ 是如何工作的。 $f$ 的定义域是 $S\times A$ ，这很容易理解，机器的变化依赖于当前状态和读到的符号。 $f$ 的值域是三个部分的积。 $S\cup\text{"Yes"}\cup\text{"No"}$ 表示在当前状态读到一个输入后，可以到"Yes"状态，表示接受，或者是"No"，表示拒绝，或者是其他 $S$ 里面其他值。接受或者拒绝是机器停机的状态，这两者不是 $S$ 的一部分，是特殊的状态。
有些图灵模型用"Halt"表示停机，我们不会使用这种表述。后续会聚焦于是否的问题上。
第二部分 $A$ 表示能够读到的符号或写的符号的集合。最后三个组成一个部分，表示读写完成之后，根据当前状态，向前或向后移动一格，或者不动。

这个定义看似太繁重，或者太广泛（包括一切算法能做的事情）。因此，大部分我们遇到的算法都能用图灵机来执行。
有一些版本对其做了增强或者简化。上面的描述常称为确定性(deterministic)图灵机，因为状态、磁头位置、磁带的内容，下一步做什么是确定的。当我们和其他机器对比时，我们会进一步解释确定性。

Example 20.1. 使用图灵机来确定正整数 $a$ 是否能被三整除。
(1) 状态集合 $S=\{start, 0, 1, 2, Yes, No\}$ (2) 符号集合 $A=\{start, blank, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, end\}$ (3) 磁带从左到右分别是 $start$ ， $a$ 的各个数字，最后是 $end$ 。
(4) 程序 $f$ 定义如下
(a) 开始磁头在 $start$ 的位置，初始状态是 $start$ 。读完 $start$ 之后，磁头右移，状态到0。
(b) 开始读 $a$ 的各个数字，如果是0, 3, 6, 9，状态不动，如果是1, 4, 7的话，状态移动一个（比如是0，变成1，如果是1，变成2，如果是2，回到0），如果是2, 5, 8的话，状态移动两个。
(c) 读到 $end$ 的时候，如果状态是0，变成Yes，否则变成No。
整个算法利用的就是能被三整除的数其数字和也能被三整除。

本章剩余部分不会再这样分析算法了。上面这个例子的目的是展示如何把算法转化成图灵机的表示方法。优势是磁头的移动能够清晰地分析算法的时间复杂度。

Complexity Classes

这一节我们会看一些非常引人入胜的问题。我们会试图去描述哪些问题可以用图灵机高效的解决。

The Class P

能用是或者否来回答的问题是判定问题(decision problem)，比如一个图是否是二分图，一个图是否是连通的，一个数是否是质数，一个排列是否包含偶数个长度为七的循环。语言 $L$ (Language)是答案是Yes的判定问题的集合。对应上面的问题，所有的二分图、连通图、质数集合、包含偶数个长度为七的循环的排列的集合都各自来自同一个语言。
给定输入 $x$ ，如果 $x\in L$ ，图灵机 $T$ 结束于Yes，否则结束于No，那么我们说图灵机 $T$ 接受 $L$ 。

Definition 20.2. 我们说 $L$ 属于 $P$ 如果存在一个图灵机 $T$ 和正整数 $k$ ，在 $O(n^k)$ 时间内 $T$ 接受 $L$ ，其中 $n$ 是输入规模。

将长度为 $n$ 的输入 $x$ 输入 $T$ ，那么磁头移动 $O(n^k)$ 就可以决定 $x\in L$ 还是 $x\notin L$ 。我们测量时间的单位是磁头移动的次数。这是一个统一的单位，对所有问题都适用。
如果 $L$ 属于 $P$ ，那么我们会说 $L$ 的成员能在多项式时间内被检测出结果。
可能会有人觉得这里太粗略了，因为 $P$ 不区分 $O(n)$ 还是 $O(n^{20})$ 。下面会给出答案。

Example 20.3. 所有包含三角的简单图组成了 $L$ ，那么 $L\in P$ 。
Solution. 简而言之，最多 $\begin{pmatrix}n\\3\end{pmatrix}=O(n^3)$ 就能确定答案。在确定一个三角形的任意两条边之间，磁头移动的距离小于 $O(n^2)$ 的。

在前面的定义中，我们没有指定 $k$ 是多少。这消除了输入规模应该多大的问题，比如是图中点的个数 $n$ 还是邻接矩阵项的个数 $n^2$ 。
我们也没有明确磁头移动这个问题。

Example 20.4. 这个问题的输入规模是 $n$ 。对于任意的 $p=p_1p_2\cdots p_n$ 。对于每一个 $i\in[n]$ ，如果 $p_i=j$ ，那么需要验证 $p_j=i$ 是否成立。这样有 $n$ 个表示是需要去验证，每次验证，磁头最多移动 $n$ 个格子，所以磁头最多移动 $O(n^2)$ 次。

$P$ 是复杂性分类中的一类。这类问题的复杂性差不多。回到前面 $P$ 不区分 $O(n)$ 还是 $O(n^{20})$ 的问题上。举个具体的例子，一个问题需要 $n$ 步去解决和需要 $n^{100}$ 步去解决是有差别的，但是这个差别远远小于和需要 $2^n$ 步才能解决的问题之间的差别。如果一个计算机能够用 $\log{m}$ 的时间解决一个 $m$ 规模的问题，那么对应前面的例子，需要的时间分别是 $\log n$ 和 $100\log n$ ，差别常数倍，但是第三个问题需要 $n\log 2$ 的时间，这个时间高一阶。更准确地说，如果 $n$ 趋于无穷，解决前两个问题的时间相比解决最后一个问题而言，可以忽略。所以我们把 $O(n)$ 和 $O(n^{20})$ 归为一类。
大致上讲， $P$ 是一类能够被高效解决的问题，需要的时间是多项式复杂度。很多场景下，这可能是我们能接受的最好结果了，因为至少需要 $n$ 来读取输入。