时间复杂度
时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。
不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序性能很好，具有$O(1)$的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是$O(n)$，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于$O(n^2)$的复杂度。还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是$O(a^n)$的指数级复杂度，甚至$O(n!)$的阶乘级复杂度。
我们将复杂度量级按照数量级递增进行排序得到下图，并将其分为两类：多项式量级和非多项式量级，后者的复杂度远远大于前者。
多项式级的复杂度包括$O(1),O(log(n)),O(n^a)$等，它的规模n出现在底数的位置；非多项式级只包含$O(a^n),O(n!)$两种，其复杂度计算机往往不能承受。
自然地，人们会想到一个问题：会不会所有的问题都可以找到复杂度为多项式级的算法呢？很遗憾，答案是否定的。举个例子，输出从1到n这n个数的全排列。不管你用什么方法，你的复杂度都是阶乘级，因为你总得用阶乘级的时间打印出结果来。
还有另外一个经典的问题：Hamilton回路。问题是这样的：给你一个图，问你能否找到一条经过每个顶点一次且恰好一次（不遗漏也不重复）最后回到起点的路径（满足这个条件的路径叫做Hamilton回路）。这个问题目前还没有找到多项式级的算法。事实上，这个问题就是我们后面要说的NPC问题。
由此，我们根据复杂度分级，将问题进行分类。最简单的一类问题被称为P问题，按复杂度依次递增，又有NP问题、NPC问题和NP-Hard问题。先来看看P问题的定义。
P问题
定义：在计算复杂度理论中，P（polynomial time class）是在复杂度类问题中可于确定型图灵机以多项式量级（或称多项式时间）求解的决定性问题。
简单来说，就是一个P问题可以在多项式（$O(n^k)$）的时间复杂度内被解决。
P问题比较容易理解，它是复杂度最低的一类问题。事实上，计算机能解决的问题绝大部分都属于P问题，譬如排序、最小树、最短路、最大流、最小费用流、最大匹配等常见问题都是多项式时间可解的P类问题。
然而另一类问题如旅行商问题(TSP)、整数线性规划问题(ILP)至今仍未找到多项式时间算法，又往往无法证明多项式算法的不存在性。在这类问题中，又存在一类特殊的问题，即：我无法在多项式时间内解决该问题，但我可以找到该问题的一个解，然后在多项式时间内验证该解是否正确。我们将这类问题归类为NP问题。举个例子，前面的Hamilton回路问题，虽然它不是P问题，但我可以找到一条路径，并在$O(n)$时间内验证这条路径是否经过每个顶点一次（每个顶点遍历一次）。
NP问题
定义：非确定多项式类（non-deterministic polynomial，缩写：NP）是指在在非确定型图灵机上可以用多项式时间复杂度的算法解决的问题。
简单来说，NP问题是指可以在多项式时间内猜出一个解或验证一个解的正确性的问题。
很显然，前面所说的Hamilton回路属于NP问题。但若是问题变成这样：试问一个图中是否不存在Hamilton回路？该问题就没法在多项式的时间里进行验证了，因为除非你验证过所有的路径，否则你不敢断定它“没有Hamilton回路”。
之所以要定义NP问题，是因为通常只有NP问题才有可能找到多项式的算法。若是一个问题连在多项式时间内验证一个解是否正确都做不到，那我们不指望能存在一个解决它的多项式级的算法。事实上信息学中的号称最困难的问题——“NP问题”，其实就是在探讨NP问题与P问题的关系。
很显然，所有的P问题都是NP问题，即$P \subset NP$。因为，如果能在多项式时间内解决一个问题，必然能在多项式时间内验证一个问题的解是否正确。那么问题就变成了：是否所有的NP问题都是P问题，即究竟是否有P=NP?
目前为止，这个问题还未被证明或推翻。但人们普遍认为，P≠NP，也就是说，多数人相信，存在至少一个不可能有多项式级复杂度的算法的NP问题。人们如此坚信P≠NP是有原因的，就是在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题，即所谓的NPC问题。正是NPC问题的存在，使人们相信P≠NP。下面我们介绍NPC问题，你从中可以体会到NPC问题使P=NP变得多么不可思议。
NPC问题
定义：如果一个问题满足：
- 它是一个NP问题。
- 其他属于NP的问题都可在多项式时间内归约成它。
我们就将这类问题称为NP-完全问题（NP-Complete，缩写为NP-C或NPC）
为了说明NPC问题，我们先引入一个概念——规约(Reducibility)。简单地说，一个问题A可以规约为问题B的含义是，可以用问题B的解法解决问题A。所以，B的时间复杂度是大于等于A的时间复杂度的。也就是说：A规约为B，B比A问题要更泛化、更难求解；但一旦B问题解决了，A问题也随之解决了。
《算法导论》上举了这么一个例子。比如说，现在有两个问题：求解一个一元一次方程和求解一个一元二次方程。那么我们说，前者可以规约为后者，意即知道如何解一个一元二次方程那么一定能解出一元一次方程。我们可以找到一个“规则”：两个方程的对应项系数不变，一元二次方程的二次项系数为0。按照这个规则把前一个问题转换成后一个问题，两个问题就等价了。同样地，我们可以说，Hamilton回路可以规约为TSP问题：在Hamilton回路问题中，两点相连即这两点距离为0，两点不直接相连则令其距离为1，于是问题转化为在TSP问题中，是否存在一条长为0的路径。Hamilton回路存在当且仅当TSP问题中存在长为0的回路。
很显然，规约具有一项重要的性质：传递性。如果问题A可规约为问题B，问题B可规约为问题C，则问题A一定可规约为问题C。当然，我们所说的“可规约”是指的可“多项式地”规约(Polynomial-time Reducible)，即变换输入的方法是能在多项式的时间里完成的。规约的过程只有用多项式的时间完成才有意义。
现在我们已经知道，一个问题规约为另一个问题，时间复杂度增加了，问题的应用范围也增大了。结合规约的传递性，通过对某类问题的不断约化，我们能够不断寻找复杂度更高，但应用范围更广的算法来代替原先复杂度较低但应用范围也更小的一类问题的算法。自然地，我们会想问，如果不断地规约上去，能否找到一个时间复杂度最高，并且能“通吃”所有的NP问题的这样一个超级NP问题？答案居然是肯定的。也就是说，存在这样一个NP问题，所有的NP问题都可以规约成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。这种问题的存在难以置信，并且更加不可思议的是，这种问题不只一个，它有很多个，它是一类问题。这一类问题就是所谓的NPC问题，也就是NP-完全问题。到这里你应该可以理解完全（Complete）的含义了。NPC问题的出现使整个NP问题的研究得到了飞跃式的发展。我们有理由相信，NPC问题是一类NP问题中最复杂的问题，也是在P≠NP假设下最不可能找到多项式时间（化简为P）的问题。
既然所有的NP问题都能规约为NPC问题，那么只要任意一个NPC问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决了，NP也就等于P了。因此，给NPC找一个多项式算法太不可思议了。因此，前文才说，“正是NPC问题的存在，使人们相信P≠NP”。我们可以就此直观地理解，NPC问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。
那么有没有比NPC问题更复杂的问题呢？答案是有的，就是我们接下来介绍的NP-Hard问题。
NP-Hard问题
定义：如果所有NP问题都可以多项式时间归约到某个问题，则称该问题为NP-困难问题（NP-hardness, non-deterministic polynomial-time hardness，缩写为NP-Hard）。
注意到，一个NP-Hard问题未必可以在多项式时间内验证一个解的正确性，即NP-Hard问题不一定是NP问题，也就是NP-Hard问题只满足NPC问题定义的第二个条件。因此我们可以将NPC问题理解为即是NP问题又是NP-Hard问题的一类问题。也就是说，NP-Hard问题要比NPC问题的范围更广。从时间复杂性上来考虑，由于NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高更难以解决。换句话说，即使NPC问题有多项式时间的解（P=NP），NP-Hard问题依然可能没有多项式时间的解。
研究生数模竞赛中遇到的基本都是NP-Hard问题，在P≠NP的假设下，只能设计启发式算法或者近似算法，求得令人满意的可行解。启发式算法是一个基于直观或经验构造的算法，在可接受的花费(指计算时间和空间)下给出待解决优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度一般不能被预计。启发式算法以仿自然体算法为主，主要有遗传算法、蚁群算法、模拟退火法、神经网络等；近似算法则可以相当快速地找到合理的解决方案，需要证明解决方案的近似性，即所有实例中最坏情况下可以保证近似解的范围，并且运行时间合理。近似算法对于任何实例通常可得到一个有质量保证的解。近似性常用近似比、近似方案来度量。近似算法往往设计方法不难，比如贪心法、动态规划、基于线性规划的方法，但近似性的证明非常难。两者相辅相成。
关系图
基于P≠NP和P=NP两种猜想，我们得到描述P, NP, NPC，以及NP-Hard之间关系的欧拉图：
可以看到，在P≠NP假设下，P与NPC没有交集，亦即我们之前提到的，NPC问题最不可能化简为P问题。而在P=NP问题下，即使是最复杂的NPC问题也可以化简为P问题，因为从定义来说NPC也是一个NP问题。
确定型与非确定型图灵机
定义中提及了确定型/非确定型图灵机，虽然对于理解P和NP问题没有太大影响，但还是有必要在这里做一个简要的阐述。
图灵机（Turing machine），又称确定型图灵机，是英国数学家艾伦·图灵于1936年提出的一种将人的计算行为抽象化的数学逻辑机，其更抽象的意义为一种计算模型，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。图灵机有以下几个组成部分：
- 一个不限长度的纸带。纸带被划分成一个个的小格子，格子中标有符号或者空白。
- 一个读写头。可在纸带上移动，能够读写格子中的符号。
- 一套控制规则。根据当前机器所处状态以及当前读写头所指的格子上的符号，来决定读写头下一步的动作，并改变状态寄存器的值。
- 一个状态寄存器。保存图灵机当前状态。
不难看出图灵机本质上就是状态机，我们可以将机器从开始运行到停机的运作过程记录为一串序列：
$$q_0 \rightarrow_{\omega_0} q_1 \rightarrow_{\omega_1} q_2 \rightarrow … \rightarrow_{\omega_{n-1}} q_n$$
开始时，机器处于$q_0$状态，读写头指向0号格子；开始运行后，读入格子中的符号$\omega_0$，根据控制规则，机器进入下一状态$q_1$；重复此过程，直至到达终止状态，机器停机。
终止状态包括两种状态，$q_{accept}$称为接受状态，即机器根据控制规则成功运行至终态；$q_{reject}$称为拒绝状态，如果在运行中遇到下一个操作没有定义的情况，机器将立刻停机并拒绝输入的字符串。由于整个过程只要初始状态、输入、控制规则确定，机器运行的过程就确定，所以我们将其称之为确定型图灵机。
如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为止。
图灵机是一个计算机的理论模型，我们通常说，现代计算机是基于冯诺依曼体系的，实际是冯诺依曼机就是基于图灵机模型的实现，包括高度复杂化的运算、控制、存储、输入、输出五个部分。比如纸带（用内存/磁盘模拟）、内部状态寄存器（现代计算机有大量的标志位和大量的寄存器甚至寄存器组）、在纸带上移动（各种跳转指令、各种复杂的寻址操作）、控制规则（CPU指令集）等。到目前为止，依然没有能够超越图灵机的模型。关于人工智能、量子计算机是否超越了图灵机也有非常有趣的讨论，感兴趣的读者可以自行查阅资料。
