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