LH (Komplexität)

Im Rechenkomplexität, das logarithmische Zeithierarchie (Lh) ist der Komplexitätsklasse von allen Rechenprobleme lösbar in a logarithmisch Menge von Berechnungszeit auf an Wechsel Turing Machine mit einer begrenzten Anzahl von Wechsel.Es ist ein besonderer Fall von a Begrenzte alternierende Turing -Maschine Hierarchie.Es ist gleich zu Fo und zu fo-uniform AC0.[1]

Das Die Ebene der logarithmischen Zeithierarchie ist die Reihe von Sprachen, die durch abwechselnde Turing -Maschinen in logarithmischer Zeit erkannt werden Zufallszugriff und Wechsel, beginnend mit einem existenzieller Zustand. Lh ist die Vereinigung aller Ebenen.

Verweise

  1. ^ Neil Immerman (1999). Beschreibende Komplexität. Springer. p.85.