Перейти к навигации Перейти к поиску
В вычислительной сложности , то логарифмическая иерархия времени ( ЛГ ) является классом сложности всех вычислительных задач решаемых в логарифмическом количестве времени вычисления на с чередованием Тьюринга машина с ограниченным числом чередований. Это частный случай иерархии ограниченных переменных машин Тьюринга . Он равен FO и FO-однородному AC0 . [1]
Й уровня логарифмической иерархии времени является множеством языков , распознаваемых чередования машины Тьюринга в логарифмическое время с произвольным доступом и чередованием, начиная с экзистенциальным государством . LH - это объединение всех уровней.
Ссылки [ править ]
- ^ Н. Иммерман (1999). Описательная сложность . Springer. п. 85 .