- Класс L
-
- Это статья о классах языков для детерминированной машины Тьюринга. Статья о unix-утилите называется — множество языков, разрешимых на детерминированной машине Тьюринга с использованием O(log(n)) дополнительной памяти для входа длинной n.
Класс языков NL — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием O(log(n)) дополнительной памяти для входа длинной n.
Примеры:
- Пусть язык PATH = {(G, s, t) : G — ориентированный граф в котором есть путь от s до t}, тогда
NL-полные задачи
Преобразователь, требующий логарифмической памяти — машина Тьюринга с тремя лентами: входной, доступной только на чтение, выходной, доступной только на запись и рабочей лентой, на которой может использоваться не более O(log(n)) ячеек.
Функция, вычисляемая таким преобразователем называется функцией, вычисляемой с логарифмической памятью.Задача A логарифмически по памяти сводится к задаче B, если есть логарифмическая по памяти функция, при помощи которой задача А сводится к задаче В. Обозначается
Язык называется NL-полным если он принадлежит NL и любой язык из NL сводится к нему логарифмически по памяти.
Теорема:
Следствие:
- Если NL-полный язык принадлежит L, то L = NL
Утверждение:
- PATH — NL-полная задача.
Следствие:
- .
Теорема Иммермана
Класс coNL — языки, дополнения до который лежат в NL.
Теорема Иммермана:
- NL = coNL
Литература
- Michael Sipser: «Introduction to the Theory of Computation»
Wikimedia Foundation. 2010.
- Это статья о классах языков для детерминированной машины Тьюринга. Статья о unix-утилите называется — множество языков, разрешимых на детерминированной машине Тьюринга с использованием O(log(n)) дополнительной памяти для входа длинной n.
Класс L
Полезное
Смотреть что такое "Класс L" в других словарях:
класс — класс, а … Русский орфографический словарь
класс — класс/ … Морфемно-орфографический словарь
КЛАСС — (в логике и математике) 1) понятие, присущее всем элементам некоторой совокупности объектов; 2) совокупность выделенных по некоторому признаку объектов, мыслимая как целое. Понятие К. (множества) обычно относят к числу простейших, неопределяемых… … Философская энциклопедия
Класс! — Класс! … Википедия
КЛАСС — (лат. classis порядок.). 1) разряд однородных предметов. 2) собрание учеников для учебных занятий, а также помещение и самое время, назначенное для урока. 3) степень в государственной службе. Словарь иностранных слов, вошедших в состав русского… … Словарь иностранных слов русского языка
класс — сущ., м., употр. часто Морфология: (нет) чего? класса, чему? классу, (вижу) что? класс, чем? классом, о чём? о классе; мн. что? классы, (нет) чего? классов, чему? классам, (вижу) что? классы, чем? классами, о чём? о классах 1. Классом называют… … Толковый словарь Дмитриева
КЛАСС — КЛАСС, [ас] класса, м. [латин. classis]. 1. Социальная группа, часть общества, объединенная общностью интересов вследствие одинакового отношения к средствам производства и противостоящая другим социальным группам в силу противоположности… … Толковый словарь Ушакова
КЛАСС! — КЛАСС! … Википедия
КЛАСС — (class) Оксфордский словарь английского языка дает следующее определение класса: Разделение общества или порядок в обществе согласно статусу; разряд, категория общества . Но это определение класса столь же разъясняет, сколь и вносит путаницу.… … Политология. Словарь.
класс — а; м. [от лат. classis разряд] 1. (чего) В научной терминологии: совокупность, группа предметов или явлений с общими признаками; разряд, категория. К. млекопитающих. К. земноводных. К. двудольных растений. Плавать на судах различных классов.… … Энциклопедический словарь
класс — См. разряд … Словарь синонимов