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

  1. ↑ «MR: Matches for: MR=1127168». [Consulta: 30 novembre 2018].
  2. ↑ «MR: Matches for: MR=1255326». [Consulta: 30 novembre 2018].
  3. ↑ 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.
  • Vegeu aquesta plantilla
Classes de complexitat
Considerades tractables
DLOGTIME  · AC0  · ACC0  · TC0  · L  · SL  · RL  · NL  · NC  · SC  · CC  · P  · P-complet  · ZPP  · RP  · BPP  · BQP  · APX
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
EXPTIME  · NEXPTIME  · EXPSPACE  · ELEMENTARY  · PR  · R  · RE  · ALL
Jerarquia de classes
Families de classes