Изменения

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