计算复杂度

本文介绍图灵机，确定性多项式时间类和非确定性多项式时间问题。

图灵机

为了精确定义有效程序(即算法)这一概念，图灵构思了一种称为图灵机(Turing machine)的计算设备，把它作为一个计算原型，但却是非常通用的计算模型。这里要介绍的计算复杂性材料沿用了图灵机计算模型。下面介绍图灵机的个变型，这对我们学习计算复杂性的目的来说已经足够了。

在我们的变型里，图灵机由有限状态控制单元、k(≥1)条纸带( tape)以及同样数量的读写头( tapehead)组成。有限控制单元控制磁头读写纸带的操作，每个读写头访问一条纸带(称为它的纸带)，沿着纸带或左或右地移动完成这一操作。每一条纸带分成无限个单元(cell)。图灵机求解一个问题时,读写头扫描一个有有限个字符的串。该串从纸带最左边的单元开始按顺序存放在纸带上，每个字符占用一个单元,右边剩下的是空白(blank)单元，该串称为问题的一个输入。扫描从含有输入的纸带左端开始，同时图灵机赋一个初态( initial state）。任何时刻图灵机都只有一个读写头访问它的纸带。读写头对它的纸带的一次访问称为一个合法移动。

如果图灵机从初始状态开始，一步接一步地合法移动，完成对输入串的扫描，最终满足了终止条件而停下来，则称图灵机识别了该输入。图灵机识别的一个输入被称为一种可识别语言（language）的一个实例。

对给定的问题，图灵机可以由它的有限控制单元的功能完全描述。这样的功能可以用一张表的形式给出，列出图灵机每个状态的下一步。

为识别一个输入，图灵机$M$在停下来之前所移动的步数称为$M$的运行时间或$M$的时间复杂性，记为$T_M$。$T_M$可以表示为函数$T_M(N):N\rarr N$，其中n是输入实例的长度或规模。当$M$在初始状态时，它就是组成输入串的字符数，$T_M(n)\ge n$。除了对时间的要求外，$M$还有对空间的要求$S_M$，它是$M$在写操作中读写头访问的纸带单元数。$S_M$可表示为函数$S_M(n):N\rarr N$，称为$M$的空间复杂性。

下面我们介绍一个具体的图灵机。

确定性多项式时间

$p(n)$是整数上关于$n$的一个多项式，它有下列形式：

$p(n)=c_kn^k+c_{k-1}n^{k-1}+...+c_1n+c_0$

其中$k,c_i$是常整数且$c_k\ne 0$，当$k>0$是，前者称为多项式$p(n)$的次数，记为$deg(p(n))$，后者称为多项式$p(n)$的系数。

P类，我们记$P$表示具有下列特征的语言类。语言$L$在$P$中，如果存在一个图灵机$M$和一个多项式$p(n)$使得对任意非负整数n，M可以在时间$T_M(n)\le p(n)$内识别任意实例$I\in L$，其中n是表示实例$I$规模的整数参数。我们称L是可以在多项式时间内识别的。

粗略地说，可以在多项式时间内识别的语言总是很容易的。