在計算複雜度理論裡面,複雜度類ELEMENTARY是所有指數譜系裡面的複雜度類聯集:
這名稱最早是為了探討可計算函數和不可判定問題,由László Kalmár所提出;most problems in it are far from elementary。Some natural recursive problems lie outside ELEMENTARY, and are thus NONELEMENTARY。相當值得注意的,有一些原始遞歸函數問題不在ELEMENTARY內。我們已知:
LOWER-ELEMENTARY EXPTIME ELEMENTARY PR
與ELEMENTARY僅包含有限的冪(例如,)比較,PR使用的 超運算更一般化(例如,tetration),因此PR不包含於ELEMENTARY。
易解复杂度类 | 对数空间相关 | - DLOGTIME
- AC0(英语:AC0)
- ACC0(英语:ACC0)
- TC0(英语:TC0)
- L · FL · SL · NL
- NC
- SC
- PolyL
|
---|
多项式空间相关 | - P(P-完全)
- FP(英语:FP (complexity))
- ZPP
- RP
- BPP
- BQP(QMA(英语:QMA)
- PostBQP(英语:PostBQP)
- EQP(英语:EQP))
|
---|
| |
---|
怀疑难解复杂度类 | - UP
- NP(NP完全
- NP困难
- 反NP
- 反NP完全(英语:co-NP-complete))
- FNP(英语:FNP (complexity))(TFNP(英语:TFNP (complexity)))
- PH
- PP
- #P(#P-完全(英语:Sharp-P-complete))
- PSPACE(PSPACE完全(英语:PSPACE-complete))
|
---|
难解复杂度类 | |
---|
复杂度类的谱系 | |
---|
相关复杂度族 | |