复杂性理论
复杂性理论是计算机理论科学的中心课题。它有直接的应用可计算性理论和使用计算模型,如图灵机帮助测试复杂性。复杂性理论帮助计算机科学家将问题联系起来,并将它们组合成复杂性类.有时,如果一个问题可以解决,它就为解决其复杂性类中的其他问题打开了一条道路。复杂性有助于确定问题的难度,通常是通过解决特定问题所需的时间和空间(内存)来衡量的。例如,有些问题可以在多项式这需要大量的时间和其他时间指数与输入大小相关的时间量。
复杂性理论也有现实世界的含义,特别是算法设计和分析。一个算法可以根据它的复杂性来分析,这经常在大0符号.通常情况下,程序员想要编写高效的算法,并且能够判断一个算法运行的时间是多项式还是指数,这可以告诉程序员他或她的算法是否是最好的选择。复杂性理论对生物学家的研究具有应用价值神经元如设计硬件的电气工程师、研究语言和语法的语言学家以及建筑物理学家量子计算机.[1]
在理论和实践中,复杂性理论帮助计算机科学家确定计算机能做和不能做的极限。
在许多情况下,问题可以建模为决策问题这些问题可以用“是”或“不是”来回答。例如,“这个数是质数吗?”,“这个图有。哈密顿路径“是否有一个变量赋值给这个方程以满足一组约束条件?”决策问题的例子包括旅行推销员问题,3坐,素性测试.决策问题可以用计算模型来模拟,例如图灵机.
复杂性理论的背景主题
复杂性类
复杂性和算法
复杂度通常用来描述算法。有人可能会听到“我的排序算法在oh of运行。 在复杂性中,这被写成 是多项式运行时间。复杂性用于描述算法中资源的使用。一般来说,关注的资源是时间和空间。一个算法的时间复杂度表示它必须完成的步骤数。算法的空间复杂度表示算法工作所需的内存数量。
算法的时间复杂度描述了相对于输入,算法需要执行多少步。例如,如果 输入的元素只被操作一次,该算法将采取 时间。例如,如果算法需要对输入的一个元素进行操作(不管输入的大小如何),这是一个常数时间,或者 ,算法,因为不管输入大小,只做一件事。如果是算法 的每个操作 元素输入到算法,然后运行该算法 时间。
在算法设计和分析中,计算机科学家会考虑三种类型的复杂性:最佳情况、最差情况和平均情况的复杂性。
最佳、最差和一般情况的复杂性
复杂性可以描述时间和空间,这个维基会用时间复杂性来描述,但同样的概念也可以应用于空间复杂性。
假设你是排序一串数字。如果输入列表已经排序,你的算法可能只需要做很少的工作——这可以被认为是“最佳情况”的输入,并且运行时间非常快。让我们使用相同的排序算法,给它一个完全向后的输入列表,每个元素都不在合适的位置。这可以被认为是“最坏情况”的输入,并且运行时间非常慢。现在,假设您有一个随机输入,它有些有序,有些无序(一个平均输入)。这将占用平均情况下的运行时间。
如果你了解你的数据,例如,如果你有理由预计,通常将主要分类列表,因此可以指望你最好的运行时间,你可能会选择一种算法和一个伟大的最好的运行时间,即使它有一个可怕的坏和平均情况运行时间。但是,程序员通常需要编写能够有效处理任何输入的算法,因此计算机科学家通常特别关注算法的最坏情况运行时间。
重要问题的复杂性
复杂性也有理论应用。计算机科学中的许多重要问题,如P与NP用复杂性理论来解释问题。许多重要的计算机科学理论问题本质上归结为
- “这两个问题可以相互简化吗?A问题的答案能帮助我们解决B问题吗?”
或
- 复杂度等级X是否等同于复杂度等级Y
对这类问题的回答通常对理论计算机科学和现实世界的应用具有深远的影响。例如,如果P被证明等于NP,我们的大多数安全算法,比如RSA就会非常容易被打破。
上世纪70年代,库克和莱文证明了这一点布尔可满足性是一个非完全多项式问题,这意味着它可以转化为NP类中的任何其他问题。换句话说,可满足性问题可以在NP中模拟任何其他问题。这向我们展示了复杂性理论的一个强大的结果:通过确定如何解决一个可满足性问题和使用Cook-Levin定理,我们知道如何处理NP中的所有其他问题。此外,这意味着如果计算机科学家想出了如何在多项式时间内解决NP竞争问题,那么所有其他NP问题都可以在多项式时间内解决,换句话说,P将等于NP。
测试的复杂性
为了“测试”一个问题的复杂性,计算机科学家们将试图解决这个问题图灵机看看决定一个问题需要多少步骤(时间复杂度)和多少磁带(空间复杂度)。
我们可以用图灵机来解实例问题或验证对这个问题提出的答案例如,问题可能是旅行推销员的问题,这个实例可能是旅行推销员正在旅行的一个特定图。旅行销售人员问题的一个例子可能是销售人员在纽约市旅行,另一个例子可能是销售人员在伦敦旅行。在这两种情况下,销售人员的目标是相同的,尽管具体的图表可能不同。
一个特定问题的运行时间,比如旅行销售人员问题,可能取决于特定的实例。例如,更大的实例可能需要更多的时间来解决。这就是为什么将给定问题的复杂性计算为特定实例大小的函数。通常,输入的大小是以位为单位度量的。一般来说,复杂性理论处理的是算法如何随着输入规模的增加而扩展。[3].实例被编码为遵循特定模式或规则的位串(类似于常规的语言和上下文无关语言.图灵机将这个问题建模为一种语言,并将输入输入到这个问题中。
当我们在图灵机维基上看到图灵机接收一个程序并根据这个程序对输入进行操作时,在复杂性证明中,我们通常只是抽象出特定的图灵机程序。的Church-Turing论文说任何可计算的问题都可以在图灵机上计算,所以我们可以有把握地假设,如果一个问题是可计算的,就会有一个针对它的程序。问题的时间复杂度是由图灵机解决问题的步骤决定的,而问题的空间复杂度是机器在纸带上需要多少空间。
参考文献
- 沙伊德尔C。复杂性理论简介.2016年7月10日,从http://www.cs.jhu.edu/~scheideler/courses/600.471_S05/lecture_1.pdf
- 雅各布斯,K。理论的计算.2016年6月26日,从http://ocw.mit.edu/courses/mathematics/18-404j-theory-of-computation-fall-2006/
- , .计算复杂性理论.2016年7月12日,从https://en.wikipedia.org/wiki/Computational_complexity_theory
- , N。文件:2 b.svg图灵机.2016年7月12日,从https://en.wikipedia.org/wiki/File:Turing_machine_2b.svg