复杂度类
在计算复杂度理论中，一个复杂度类指的是一群复杂度类似的问题的集合。一个典型的复杂度类的定义有以下形式：
例如NP类别就是一群可以被一非确定型图灵机以多项式时间解决的决定型问题。而P类别则是一群可以被确定型图灵机以多项式时间解决的决定型问题。某些复杂度类是一群函数问题的集合，例如FP (复杂度)。
复杂度类之间的关系
下表简列了一些属于复杂度理论的问题（或语言、文法等）类别。如果类别X是类别Y的子集合，则X将会画在Y底下，并以一黑线相连。如果X是子集合，但不知是否与Y相等，则以较轻的虚线相连。实际上可解与不可解问题更属于可计算性理论，但是它有助于更透彻了解复杂度类的问题。
|
|||||||||
 |
|
||||||||
|
|
||||||||
|
|||||||||
|
|||||||||
|
|||||||||
|
|||||||||
 |
|||||||||
|
|||||||||
|
|||||||||
|
|||||||||
|
|||||||||
|
|||||||||
|
|
|
|
|
|||||
|
|
|
|
|
|||||
|
|
|
|
|
|||||
|
|
|
|
|
|||||
|
|
|
|
|
|||||
|
|
|
|
|
|||||
|
|
|
|
|
|||||
|
|
|
|||||||
|
|
|
|||||||
|
|
||||||||
|
|
||||||||
|
|||||||||
|
|||||||||
|
|||||||||
扩展阅读
- 复杂度类大观园 （页面存档备份，存于互联网档案馆）：一个巨大的复杂度类列表，专家级使用。
- 复杂度类架构图，由Neil Immerman制作，展示复杂度类的层次结构架构与它们是如何定位的。
- Garey, Michael R.与David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. NP-complete（NPC问题是解决某些数学难题的重要关键，这问题暗示人们是否可以将某些算法的执行效率提升到可接受的范围）问题的标准指南。
参见
| ||||||||||||||||||||||||||||||||||||
