补充资料：复杂性理论

复杂性理论
complexity theory

复杂性理论[~ple对ty the《玛r;叨。撇“ocT“T印p“皿l【补注】把数学问题分为可判定的和不可判定的，这是最基本的分类.这种分类对「劝阻设计太广泛的系统，例如判定程序等价性或程序停机的系统的企图，也具有一定的实践意义. 但在许多方面这种分类太粗糙.下面讨论用可判定问题的复杂性来对它们分类.两个都是可判定的问题，一个可以比另一个计算起来难得多，实际土可以认为这问题是汗可判定的.例如，合理的问题也许儿秒可以算出，而另一些问题(即使用最好的机器)可能要算儿百万年.显然，同前者比较，后者是难处理的，因此，在知道特定问题的可判定性后，还必须研究它的早参件(①mplexlty)，即问题的特定例子处理起来很困难.复杂性的考虑有决定性的重要性，例如在密码学(cryptography)中，如果不能在一定时间内破译一个情报可能会耽误整个事情，因为时间一过情况会整个改变.有关材料也在算法的计算复杂性(a 190-rithm，。。rOPutat生onal complexity of an)中讨论. 计算复杂性理论中典型的问题是:(对同一问题)算法(algorithm)4，在用更少的资源(例如时间或存储空间)的意义下是否比算法通:更好?间题尸是否有最好的算法?间题尸是否比问题尸，在如下意义下更困难:解P的一切算法比解尸，的某个固定的合理的算法都更复杂? 通过考虑T硕ng机(Turing machine)可得到自然的复杂性度量:(就输入长度而言)计算要求多少步?这是时间资源观念的自然描述.同样，在计算过程中访问的方格数目形成自然的空间度量.(见形式语言(formal langLla罗s)毛自动机(automata)和可计算函数(comPutable血nction).) 这种面向机器的复杂性将在本条下半部分考虑.讨论将限于基本’r盯ing机模型.像有多带多读头机器或随机读写机器这些变型在更详细的和特定的计算复杂性考虑中是重要的.但从最基本的结果来看，特殊的Turing机模型的选择是无关紧要的. 本条前半部分要研究公理化复杂性理论.不定义特殊的复杂性度量，例如时间或存储空间，而代之以算法使用的“抽象资源”.所用的公理很自然.在不涉及很多东西的意义上它是很弱的但在这些公理的基础上可以建立卓越的理论.这理论始于阵耳 计算复杂性理论的第三个主要方面:低层次复杂性，或某些特殊的实践中重要的算法的复杂性，则完全不讨论.这些主题以及复杂性理论更广及更高深发展的详细内容可以参阅「Asl一队71. 考虑所有的Turing机的一个枚举(enumeration) 厂M!，t‘，’rM，二陈l)枚举(AI)决定所有的单变元部分递归函数(p盯tlalre。

说明：补充资料仅用于学习参考，请勿用于其它任何用途。