在計算複雜度理論內,NSPACE(f(n))這個複雜度類是一個決定性問題的集合,裡面的問題可以以非確定型圖靈機使用O(f(n))這麼多空間,不限制時間來解決。或者,換句話說,這是DSPACE的非確定型版本。
有一些重要的複雜度類可以使用NSPACE來定義。這些複雜度類包括了:
- REG = DSPACE(O(1)) = NSPACE(O(1)),這裡 REG是正則語言(regular language)的複雜度類(非確定的特性在常數空間之內並沒有增加計算的能力)。
- NL = NSPACE(O(log n))
- CSL = NSPACE(O(n)),這裡CSL是上下文有關語言(context-sensitive language)的複雜度類。
- PSPACE = NPSPACE =
- EXPSPACE = NEXPSPACE =
最後兩個結論是從薩維奇定理導出,這定理指出對任何f(n) ≥ log(n),
- NSPACE(f(n)) ⊆ DSPACE(f2(n))。
Immerman–Szelepcsényi定理則指出對任何s(n) ≥ log n,NSPACE(s(n))在補集運算下封閉(closed under complement)。
NSPACE可以與DTIME作連接如下: 對任何space constructible function s(n),
參考資料
Complexity Zoo: NSPACE(f(n)).
易解复杂度类 | 对数空间相关 | - 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))
|
---|
难解复杂度类 | - EXPTIME
- NEXPTIME
- EXPSPACE
- ELEMENTARY
- PR
- R
- RE
- ALL
|
---|
复杂度类的谱系 | |
---|
相关复杂度族 | - DTIME
- NTIME
- DSPACE(英语:DSPACE)
- NSPACE
- 可能性核对证明(英语:Probabilistically checkable proof)
- 交互式证明系统
- 量子复杂性理论
|