复杂性理论

复杂性理论是理论计算机科学的中心课题。它有直接的应用可计算性理论和使用计算模型等图灵机帮助测试复杂性。复杂性理论帮助计算机科学家将问题联系起来，并将问题分组复杂性类．有时，如果一个问题可以解决，它就打开了解决复杂性类中的其他问题的方法。复杂性有助于确定问题的难度，通常通过解决特定问题所需的时间和空间(内存)来衡量。例如，有些问题可以在多项式大量的时间和其他需要指数相对于输入大小的时间量。

复杂性理论也有现实世界的含义，特别是算法设计和分析。一个算法可以根据它的复杂度来分析，这在大0符号．通常情况下，程序员希望编写高效的算法，并且能够判断一个算法是在多项式时间内运行还是在指数时间内运行可以告诉程序员他或她的算法是否是最佳选择。复杂性理论对生物学家的研究有一定的应用价值神经元设计硬件的电气工程师，研究语言和语法的语言学家，以及建筑的物理学家量子计算机．^[1]

在理论和实践中，复杂性理论帮助计算机科学家确定计算机能做什么和不能做什么的极限。

在许多情况下，可以将问题建模为决策问题这些问题可以用"是"或"不是"来回答例如，“这个数是质数吗?”，这个图是否有一个哈密顿路径“是否有一个变量分配到方程中，以满足一组约束条件?”决策问题的例子包括旅行推销员问题，3坐,素性测试．决策问题可以用诸如图灵机．

复杂性理论可能是理论计算机科学中最具挑战性的课题之一，因为它需要相当多的背景知识。要真正理解复杂性理论，我们应该熟悉以下主题:

常规的语言，上下文无关文法,上下文无关语言．这些主题提供了描述复杂性理论所处理问题的词汇。

图灵机是测试问题属于复杂性层次结构的常用模型，所以你应该熟悉图灵机的定义和工作方式。

这里是一个简短的概述复杂性类，在其维基页面上找到更多信息。

复杂性类用于将需要相似数量资源的问题分组在一起。例如，可以在多项式时间内解决的一组问题被认为是p类的一部分。占用指数量空间的一组问题被认为是EXPSPACE类。有些类包含在其他类中——例如，如果一个问题可以在多项式时间内解决，那么它当然也可以在指数时间内解决。下图描述了许多常见的复杂性类之间的关系。

^[２]

确定类是否等价，而不是仅仅包含在另一个类中是理论计算机科学中的一个关键问题。这张图片展示了许多流行的关系复杂性类．

复杂度常被用来描述算法。有人可能会听到这样的话:“我的排序算法运行在 $n ^ 2$时间”的复杂性，这被写成 $O (n ^ 2)$它是一个多项式运行时间。复杂度用来描述算法中的资源使用情况。一般来说，所关注的资源是时间和空间。一个算法的时间复杂度表示它必须完成的步骤数。算法的空间复杂度表示算法工作所需的内存量。

一个算法的时间复杂度描述了一个算法相对于输入需要执行多少步。例如，如果每一个 $n$输入的元素只操作一次，这个算法将 $O (n)$时间。例如，如果算法需要操作一个输入的一个元素(不管输入的大小)，这是一个常数时间，或者 $O (1)$算法，因为不管输入的大小，只做一件事。如果一个算法 $n$的操作 $n$输入到算法的元素，然后该算法运行 $O (n ^ 2)$时间。

在算法设计和分析中，计算机科学家会考虑三种类型的复杂性:最佳情况、最坏情况和平均情况复杂性。

最佳、最差和平均情况复杂性

复杂性可以描述时间和空间，本维基将从时间复杂性的角度讲，但同样的概念也可以应用于空间复杂性。

假设你是排序一串数字。如果输入列表已经排序，您的算法可能没有什么工作要做——这可以被认为是一个“最佳情况”输入，将有非常快的运行时间。让我们用同样的排序算法，给它一个完全反向的输入列表，每个元素都不合适。这可以被认为是“最坏情况”的输入，运行时间会非常慢。现在假设您有一个随机输入，它有些有序，有些无序(平均输入)。这将占用一般情况下的运行时间。

如果您对数据有所了解，例如，如果您有理由预期您的列表通常是排序的，因此可以依靠您的最佳情况运行时间，那么您可能会选择具有良好的最佳情况运行时间的算法，即使它具有糟糕的最差情况和平均情况运行时间。通常情况下，程序员需要编写能够有效处理任何输入的算法，因此计算机科学家通常特别关注算法的最坏情况运行时间。

复杂性在理论上也有应用。计算机科学中的许多重要问题，例如P与NP运用复杂性理论对问题进行了解释。许多重要的计算机科学理论问题本质上归结为

• “这两个问题可以相互简化吗?A问题的答案能帮助我们解决B问题吗?”

或

• “X类复杂性等同于Y类复杂性吗?”

这类问题的答案通常对理论计算机科学和现实世界的应用有深远的影响。例如，如果P被证明等于NP，我们的大多数安全算法，比如RSA，会非常容易被破坏。

20世纪70年代，库克和莱文证明了这一点布尔可满足性是一个非完全多项式问题，这意味着它可以转化为NP类中的任何其他问题。换句话说，可满足性问题可以模拟NP中的任何其他问题。这向我们展示了复杂性理论的一个强大结果:通过确定如何解决一个可满足性问题和使用Cook-Levin定理，我们知道如何处理NP中的所有其他问题。此外，这意味着，如果计算机科学家找出了如何在多项式时间内解决NP竞争问题，那么NP中的所有其他问题都可以在多项式时间内解决，换句话说，P将等于NP。

为了“测试”一个问题的复杂性，计算机科学家将尝试在一个图灵机看看需要多少步骤(时间复杂度)和多少磁带(空间复杂度)来决定一个问题。

我们可以用图灵机来解决实例一个问题或验证对这个问题提出的答案。例如，问题可能是旅行的销售人员问题，实例可能是旅行的销售人员正在旅行的一个特定图。旅行销售人员问题的一个实例可能是销售人员在纽约市旅行，另一个实例可能是销售人员在伦敦旅行。在这两种情况下，销售人员的目标是相同的，尽管具体的图表可能不同。

特定问题的运行时间，如出差销售人员问题，可能取决于特定的实例。例如，较大的实例可能需要更多的时间来解决。这就是为什么给定问题的复杂性是根据特定实例的大小来计算的。通常，输入的大小是用比特来衡量的。一般来说，复杂度理论处理的是算法如何随着输入大小的增加而扩展。^[3]．实例被编码为遵循特定模式或规则的比特字符串(类似于常规的语言而且上下文无关语言．图灵机将把这个问题建模为一种语言，并为这个问题提供输入。

虽然我们在图灵机维基上看到图灵机接收一个程序，并根据该程序对输入进行操作，但在复杂性证明中，我们通常只是抽象出特定的图灵机程序。的Church-Turing论文说任何可计算的问题都可以在图灵机上计算，所以我们可以有把握地假设，如果一个问题是可计算的，就有针对它的编程。一个问题的时间复杂度是由图灵机解决这个问题需要多少个步骤决定的，而问题的空间复杂度是由图灵机需要多少个磁带空间决定的。

^[4]

1. 沙伊德尔C。1复杂性理论导论．检索自2016年7月10日http://www.cs.jhu.edu/~scheideler/courses/600.471_S05/lecture_1.pdf
2. 雅各布斯,K。理论的计算．检索自2016年6月26日http://ocw.mit.edu/courses/mathematics/18-404j-theory-of-computation-fall-2006/
3. ， ．计算复杂性理论．检索自2016年7月12日https://en.wikipedia.org/wiki/Computational_complexity_theory
4. , N。文件:2 b.svg图灵机．检索自2016年7月12日https://en.wikipedia.org/wiki/File:Turing_machine_2b.svg