3.1.1　计算复杂度和图灵机

在衡量计算机的性能时，计算机进行计算使用的内存量被定义为空间资源；另一个重要资源是时间资源，是指计算机在计算上花费的时间，可用比较简单的方法来对某个计算问题所花费的时间资源进行估计，即算法复杂度。例如，对两个长度为n位的数字进行相乘计算，在一台计算机上可能需要2n2+1个时间单位，在另一台计算机上可能需要4n3+2n+3个时间单位。事实上，很难准确、详尽地计算每个问题所花费的时间，因此通常使用一种较为简单的方法来估计，即忽略常数乘法，只考虑最高阶部分，去除常数因数。在上述例子中，第一台计算机的计算时间被记为O(n2)，第二台计算机的计算时间被记为O(n3)。

在统计计算机的计算时间时，主要有以下几个问题：

（1）P问题。P是多项式（Polynomial）的缩写。P问题是指在多项式axn+bxn-1+…+c时间内必然能够解决的问题。为什么要界定P问题呢？这是因为算法复杂度的时间比多项式时间还要多的算法，是没有实际计算意义的。

（2）NP问题。NP是非确定性多项式（Nondeterministic Polynomial）的缩写。NP问题是指可以在多项式时间内验证并得出至少一个正确解的问题。一个著名的NP问题是旅行推销员问题。

（3）NPC问题。NPC是非确定性多项式完全（Nondeterministic Polynomial Complete）的缩写，是NP问题的子集，是指可以通过多项式时间归约成NP问题的问题。

（4）BPP问题。BPP是有限错误概率多项式时间（Bounded-Error Probabilistic Polynomial Time）的缩写，是指在多项式时间内可以用概率图灵机解决的问题，并且对于所有的输入，输出结果有错误的概率在1/3之内。

（5）图灵机。图灵机是指一种计算模型，由有限的一组状态和一个无限的“磁带”组成。通过使用可移动的头部（设备），图灵机可对有限的字母符号进行写入或读取。图灵机通常还包括一个转换函数，给出指向当前状态的头部（设备）对应的下一个状态。通用图灵机的操作是完全确定的，例如，用q代表头部的当前状态，s代表当前存储单元内容，d代表左移（取值为L时）、右移（取值为R时）或不动（取值为N时），当给定q和s时，下一个状态的q′、s′以及头部的运动状态d将是完全确定的。

（6）邱奇-图灵理论。当且仅当可以在非常简单的图灵机上解决某个数学难题时，才可以在任何计算机上解决该问题。换句话说，所有可以有效计算的函数都可以用图灵机来计算。这里的图灵机是指一种数学上的抽象，而不是物理设备。

（7）概率图灵机。概率图灵机（Probabilistic Turing Machine）是指一种能够在每个步骤中进行二进制随机选择的机器。在某些问题上，如寻找以质数的模平方根[1]，可以使用概率图灵机来有效解决，但使用通用图灵机就无法有效解决。概率图灵机的操作是不确定的，例如，当给定q和s时，概率图灵机会以一定的概率（而不是百分之百确定）变换到下一个状态q′、s′以及头部的运动状态d。该概率由概率函数X(q,s,q′,s′,d)来决定，X的取值是0～1之间的实数。

由于经典物理学不能充分有效地表述和模拟量子物理学，因此需要一种能够表述和模拟（包括量子设备在内）任意现实物理情况的计算模型。邱奇-图灵理论需要进一步扩展，通过加入量子图灵机来模拟所有物理系统，也就是使用量子图灵机来取代概率图灵机。

（8）量子图灵机。量子图灵机（Quantum Turing Machine，QTM）是用来表示量子计算能力的抽象机器。相对于概率图灵机而言，量子图灵机的概率部分变成了量子状态，例如，q、s、q′、s′相应地变成了量子状态，而概率函数X(q,s,q′,s′,d)变成了取值为复数的概率幅度函数。

（9）BQP问题。BQP是有限错误量子概率多项式时间（Bounded-Error Quantum Polynomial Time）的缩写，是量子计算机在多项式时间内可以解决的一类决策问题，所有实例的错误概率至多为1/3，是BPP问题的量子类比。