165
правок
Изменения
Нет описания правки
Класс языков '''L''' — множество языков, разрешимых на детерминированной машине Тьюринга с использованием ''O''(log ''n'') дополнительной памяти для входа длинной ''n''.
Иначе говоря, языки должны быть разрешимы на ''RAM''-машинах, использующих конечное число переменных.
Обобщением класса '''L''' является класс '''[[Класс NL|NL]]''' — отличие состоит в использовании недетерминированной машины Тьюринга. Разумеется, что '''L''' ⊆ '''NL'''.
