【转帖】计算复杂性理论

huangyhg

计算复杂度理论（Computational complexity theory）是计算理论的一部分，研究计算问题时所需的资源。最常见的资源是时间（要通过多少步才能解决问题）和空间（在解决问题时需要多少内存）。其他资源亦可考虑，例如在并行计算中，需要多少并行处理器才能解决问题。

时间复杂度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要参数。时间复杂度越小，说明该算法效率越高，则该算法越有价值。

空间复杂度是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数。它是算法优劣的重要度量指标，一般来说，空间复杂度越小，算法越好。我们假设有一个图灵机来解决某一类语言的某一问题，设有X个字（word）属于这个问题，把X放入这个图灵机的输入端，这个图灵机为解决此问题所需要的工作带格子数总和称为空间。

复杂度理论和可计算性理论不同，可能性理论的重心在于问题能否解决，不管需要多少资源。

huangyhg

计算复杂性导论
计算复杂性
计算复杂性理论
------参考书籍

huangyhg

　计算复杂性理论



　　computational complexity theory



　　计算机科学中研究数学问题的内在难度的理论。一个问题的难度反映在求解该问题所花费的计算资源的多少之上 ，常用的计算资源有：计算所需的时间，计算所需的存储空间等。对计算复杂性的研究能够使人们弄清被求解问题的固有难度，评价某个算法的优劣，或者获取更高效的算法。



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



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



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



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



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



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