计算复杂性理论

　　计算复杂性理论（汉语拼音：jì suàn fù zá xìng lǐ lùn），（computational complexity theory），计算机科学中研究数学问题的内在难度的理论。一个问题的难度反映在求解该问题所花费的计算资源的多少之上，常用的计算资源有：计算所需的时间，计算所需的存储空间等。对计算复杂性的研究能够使人们弄清被求解问题的固有难度，评价某个算法的优劣，或者获取更高效的算法。

　　为了研究计算复杂性，首先需要一个计算模型，用以说明哪种操作或步骤是许可的，以及它们的费用是多少。常用的计算模型有图灵机、随机存取机、组合线路等。通过这些计算模型可以研究问题复杂性的上界和下界，或寻求最佳算法。

　　问题的计算复杂性是问题规模的函数，故对一个问题需要首先定义规模。例如对于矩阵运算，矩阵的阶数可被定义为问题的规模。如果求解一个问题需要的运算次数或步骤数是问题规模N的指数函数，则称该问题有指数时间复杂性；如果所需的运算次数是N的多项式函数，则称它有多项式时间复杂性。

　　一般认为，具有多项式时间算法的问题是易解的问题；具有多项式时间复杂性的算法是好的算法。在计算复杂性理论中，把具有多项式时间复杂性的问题类记为P。有许多问题，对它们已知的最好的算法也具有指数时间复杂性。在组合学、图论、运筹学等领域存在大量这样的问题，我们并不知道对这些问题是否存在多项式时间算法。特别需要指出的是，在现实中有一大类这样的问题，它们的计算复杂性具有等效性，如果能用多项式时间解决它们当中的一个问题，则它们全部都能用多项式时间求解。这样的问题类称为NP-完全问题类。关于NP-完全问题类的研究是计算复杂性理论中的一个难点。

　　对于某个具体问题，其复杂性上界是已知求解该问题的最快算法的费用，而复杂性下界只能通过理论证明来建立。证明一个问题的复杂性下界就需要证明不存在任何复杂性低于下界的算法。显然，建立下界要比确定上界困难得多。

　　算法设计与分析是计算机科学的重要组成部分，从计算复杂性的角度看，算法设计与分析的主要任务就是建立问题复杂性的上界。设n表示问题的规模，以下是几个常见的问题及其复杂性上界：①n维快速傅里叶变换需要O（nlogn）次算术运算。②n位数的乘法在多带图灵机上需时O（nlognloglogn）。③n阶方阵乘法需要O（n2.496）次算术运算。④n位数是否为素数的判别需时O（nclogloglogn）。

　　寻求某个问题的计算复杂性上界，只要研究一个算法的复杂性即可。但是要寻求同一问题的计算复杂性下界，则必须考察所有的解决该问题的算法，这是不可能的，因此，确定计算复杂性下界只能靠理论证明。常用的确定下界的方法是对角线论证，使用这种方法可证明某些问题是不能用算法求解的。