DLOGTIME
En teoria de la complexitat, la classe de complexitat DLOGTIME és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing en un temps logarítmic. S'ha de definir amb una màquina de Turing d'accés aleatori, ja que d'altra manera la longitud de la cinta d'entrada seria més llarg que el rang màxim al que pot accedir la màquina.[1][2]
DLOGTIME-uniforme és important en el camp de la complexitat de circuits.[3]
Referències
[modifica]- ↑ «MR: Matches for: MR=1127168». [Consulta: 30 novembre 2018].
- ↑ «MR: Matches for: MR=1255326». [Consulta: 30 novembre 2018].
- ↑ Iwama, K.; Iwamoto, C. «Parallel complexity hierarchies based on PRAMs and DLOGTLME-uniform circuits» (en anglès). Proceedings of Computational Complexity (Formerly Structure in Complexity Theory). DOI: 10.1109/ccc.1996.507665.
| Considerades tractables | |
|---|---|
| Suposadament intractables | UP · NP · NP-complet · NP-hard · co-NP · co-NP-complet · AM · QMA · PH · ⊕P · PP · ♯P · ♯P-complet · IP · PSPACE · PSPACE-complet |
| Considerades intractables | |
| Jerarquia de classes | |
| Families de classes | |
