复杂度类列表.doc

复杂度类列表多项式时间（Polynomial time）在计算复杂度理论中，指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数。任何抽象机器都拥有一复杂度类，此类包括可于此机器以多项式时间求解的问题。以数学描述的话，则可说m(n)=O(nk)，此 为一常数值（依问题而定）。决定性问题（Decision problem）是一个在某些形式系统（Formal System，包含字母、字的集合及由关系组成的有限集合）回答是或否的问题。决定性问题在数学问题是否“可决定”中出现，即是否存在有效方法判定一个性质的存在性。数学中许多重要的问题都是不可决定的。以多项式时间解决的决定性问题，其属于的复杂度类被称为P。可以在多项式时间验证答案的非决定性问题称为NP。P指多项式时间（Polynomial），一个复杂问题如果能在多项式时间内解决，那么它便被称为P问题，这意味着计算机可以在有限时间内完成计算。NP指非确定性多项式时间（Non-deterministic polynomial），一个复杂问题不能确定在多项式时间内解决。所谓非确定性，就是指可以用一定数量的运算去解决多项式时间内可解决的问题。NP 问题通俗来说是其解的正确性能够被“很容易检查”的问题，这里“很容易检查”指的是存在一个多项式检查算法。假如NP问题能找到算法使其在多项式时间内解决，也就是证得了P=NP。P问题为NP问题的一个子类。（克雷数学研究所悬赏给出的21世纪七大数学猜想，其中有一个问题即为 P与NP问题的等价问题。）比NP问题更难的则是NP完全（完备）和NP-hard。若NP中所有问题到某一个问题是图灵可归约的，则该问题为NP困难问题（NP-Hard或NPH），反之则为NP完全问题（NP-Complete或NPC）。NPC则是一类目前大家认为没有多项式算法去解决的问题，但是如果你给出了这类问题的一个答案，我可以在多项式时间内验证给出的答案是否正确。NP-hard指的是至少和NP完全问题一样难的问题。注意，NP-hard问题有可能比NP完全问题难，但却不会比它容易。它们之间的关系：NPC是NP的一个子类，它是NP问题中最难的一类问题。NPH和NPC有交集，但并不同，它还包含一类比NPC更难的问题。许多复杂度类都有一个前面加上Co的同伴，这是包含原来复杂度类里面所有问题的补集的一个复杂度类。像是，若一个语言属于NP，则此语言的补集则属于Co-NP。 (注意这里不代表NP的补集就等同于Co-NP - 有一些语言同时是NP也是Co-NP，也有语言两者皆非。)一个复杂度类里面最难的问题代表这个复杂度类里面所有的问题都可以归约为这个问题。此外，归约过程本身是这个复杂度或者比他更简单的问题类别里面。如果找不到想要看的复杂度类(例如说找不到Co-UP)，那可以寻找看看这一个类别的同伴(以刚刚的例子来说：UP)来参考。#P计算NP问题的解答个数#P-完全#P问题里面最难的问题集合2-EXPTIME在双指数时间内可以解决AC0一个有限制深度的线路复杂度类。AC一种线路复杂度类AH算术阶层(arithmetic hierarchy)的复杂度类AP使用交替式图灵机在多项式时间之内可以解决的问题1AM以亚瑟梅林协定在多项式时间内可以解决的问题1BPL随机算法在多项式时间与对数空间内可以解答的问题集合 (解答或许不正确)BPP随机算法在多项式时间内可以解答的问题集合 (解答或许不正确)BQP量子电脑在多项式时间内可以解答的问题集合 (解答或许不正确)反NP使用非决定型图灵机可以在多项式时间内检查输出将为NO的问题反NP完全Co-NP问题里面最难的问题集合DSPACE(f(n)使用决定型图灵机在O(f(n)空间里面可以解决的问题DTIME(f(n)使用决定型图灵机在O(f(n)时间里面可以解决的问题E可以用指数时间，在线性指数之下，解决的问题ELEMENTARY在指数层级(exponential hierarchy)里面所有复杂度类的联集ESPACE可以用指数空间，在线性指数之下，解决的问题EXPEXPTIME的另一种称呼EXPSPACE在指数大小空间内可以解决的问题EXPTIME在指数大小时间内可以解决的问题FNP相类于NP的功能性问题版本FP相类于P的功能性问题版本FPNPPNP的功能性问题版本，又名NP-易；有名的旅行推销员问题属于这一类IP使用交互式证明系统可在多项式时间内解决的问题L可以在对数(小)空间内解决的问题LOGCFL可以在对数空间内归约为上下文无关语言MA使用梅林亚瑟协定在多项式时间内可以解决的问题NC用平行电脑可以有效率(换句话说，在多项式对数时间，polylogarithmic time，之内)解决的问题NE可以用指数时间，在线性指数之下使用非确定型图灵机解决的问题NESPACE可以用指数空间，在线性指数之下使用非确定型图灵机解决的问题NEXPNEXPTIME的别名NEXPSPACE使用非决定型图灵机在指数空间内可以解决的问题NEXPTIME使用非决定型图灵机在指数时间内可以解决的问题NL正确的解答可以在对数时间内被检查完毕NONELEMENTARYELEMENTARY的补集NP正确的解答可以在多项式时间内被检查完毕(参见复杂度类 P 与 NP的关系)NP-完全NP里面最难的问题集合NP-易（或称NP-容易）FPNP的别名NP-等价FPNP里面最难的问题，同时是NP-易也是NP-难的问题NP困难NP-完全或者更难的问题NSPACE(f(n)以O(f(n)这么多空间使用非决定型图灵机可以解决的问题NTIME(f(n)以O(f(n)这么多时间使用非决定型图灵机可以解决的问题P以多项式时间使用一般图灵机可以解决的问题P-完全在P复杂度里面，从平行电脑的角度看，最难解决的一类问题PH在polynomial hierarchy里面所有类别的联集PNP使用一个可以解决一种NP问题的神谕，则可以在多项式时间内解决的问题；也叫做2PPP概率多项式时间 (答案有稍多于的机会是正确的)PSPACE在多项式大小的内存内可以解决的问题PSPACE-完全PSPACE问题里面最难的问题R有限时间内可以解决的问题RE若答案为YES我们在有限时间内可以知道，但是若答案为NO我们可能永远算不出来的问题RL使用随机算法在对数大小