ЛХ (сложность)

В вычислительной сложности логарифмическая временная иерархия ( LH ) — это класс сложности всех вычислительных задач , решаемых за логарифмическое количество вычислительного времени на попеременной машине Тьюринга с ограниченным числом чередований. Это частный случай ограниченной альтернирующей иерархии машин Тьюринга . Он равен FO и FO-равномерному AC ⁰ .

The $i$Уровень логарифмической временной иерархии — это совокупность языков, распознаваемых попеременными машинами Тьюринга за логарифмическое время со произвольным доступом и $i-1$ чередования, начиная с экзистенциального состояния . ЛХ – это объединение всех уровней.