复杂性类

计算复杂度理论中,一个复杂度类指的是一群复杂度类似的问题的集合。一个典型的复杂度类的定义有以下形式:

可以被同一个抽象机器M使用O(f(n))的资源R所解决的问题的集合(n是输入资料的大小)。

例如NP类别就是一群可以被一非确定型图灵机多项式时间解决的决定型问题。而P类别则是一群可以被确定型图灵机多项式时间解决的决定型问题。某些复杂度类是一群函数问题的集合,例如FP (复杂度)英语FP (complexity)

许多复杂度类可为数学逻辑所描述刻划,请见描述性复杂度英语descriptive complexity

布卢姆复杂度则不需实际抽象机器就可定义复杂度类。

复杂度类之间的关系

下表简列了一些属于复杂度理论的问题(或语言、文法等)类别。如果类别X是类别Y子集合,则X将会画在Y底下,并以一黑线相连。如果X是子集合,但不知是否与Y相等,则以较轻的虚线相连。实际上可解与不可解问题更属于可计算性理论,但是它有助于更透彻了解复杂度类的问题。

决定性问题
   
类型0(递归可枚举)
未决定问题
 
递归
 
EXPSPACE
 
NEXPTIME
 
EXPTIME
 
PSPACE
         
类型1(上下文有关)
       
         
   
反NP
BQP
NP
         
     
BPP
 
         
   
P
     
 
NC
   
类型2(上下文无关)
 
类型3(正则)

扩展阅读

  • 复杂度类大观园页面存档备份,存于互联网档案馆):一个巨大的复杂度类列表,专家级使用。
  • 复杂度类架构图,由Neil Immerman英语Neil Immerman制作,展示复杂度类的层次结构架构与它们是如何定位的。
  • Garey, Michael R.英语Michael GareyDavid S. Johnson英语David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. NP-complete(NPC问题是解决某些数学难题的重要关键,这问题暗示人们是否可以将某些算法的执行效率提升到可接受的范围)问题的标准指南。

参见