在複雜度理論內,DLOGTIME是一個複雜度類,其問題可以用決定型圖靈機,在對數成長的時間內解決。這是使用決定型時間,所能定義出最小且非單純(non-trivial)的複雜度類。這類複雜度一定使用隨機存取圖靈機來定義,因為機器沒有足夠的時間來讀取整個輸入(輸入的大小,成長率是O(n))。
DLOGTIME-均一性(uniformity)在電路複雜性裡面是很重要的。
詢問輸入字串的長度這個問題屬於DLOGTIME,因為我們可以對可能的輸入大小進行折半搜索演算法(binary search)。
|
---|
| 易解复杂度类 | 对数空间相关 | - 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))
|
---|
| 难解复杂度类 | |
---|
| 复杂度类的谱系 | |
---|
| 相关复杂度族 | |
---|
|