1.4　计算复杂性

一般说来，证明一个算法的正确性，通常要使用形式化证明方法和推理证明。而其中一个重要工作就是分析算法的复杂度。在计算机科学研究领域，计算复杂性理论中的时间复杂度反映了算法执行所需要的时间，是衡量一个算法性能的重要参数。其值越小，说明这个算法效率越高。在算法的时间复杂度定义中，比较常见的有常数时间、线性时间、多项式时间及指数时间。一般而言，容易计算和难计算的边界在多项式时间和指数时间之间。在多项式时间内求解问题的算法是有效算法，并把这类问题称为P类问题，而把指数时间复杂度的算法称为NP难问题。命题P≠NP已成为数学中最有名的问题之一。

在复杂性理论中，一般都会研究判定性问题，即对于一个问题，其最后的计算结果只能为“是”或者“否”两者之一。对于确定性算法，当搜索完所有计算树分支后才能得到答案，这个计算过程长度与搜索树的顶点数成正比；而对于非确定性算法，只要搜索到其中一个树的分支为问题的解后就得出答案，这个计算过程长度与搜索树的深度成正比。该计算过程只需求出问题存在一个解即可，而不关注其他没有给出肯定答案的计算。本书会涉及对NP完全问题进行求解，比如SAT问题、三着色问题等。对于这些问题，只需要给出求解问题的“是”或者“否”之一作为该问题的计算结果即可。