Перейти на главную страницу сайта


загрузка...

Классы L и NL

Это статья о классах языков для детерминированной машины Тьюринга. Статья о unix-утилите называется nl.

Класс языков L — множество языков, разрешимых на детерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной n.

Класс языков NL — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной n.

Примеры:

  • Пусть язык — ориентированный граф в котором есть путь от 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»
п·о·р
Классы сложности алгоритмов
 
Cчитаются лёгкимиP • L • NL • AC • NC • P-C • BQP • BPP • RP • ZPP
Cчитаются сложнымиNP • co-NP • NP-C • co-NP-C • UP • #P • #P-C • IP=PSPACE • PSPACE-C • EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-C • Co-RE-C • R • PP • PCP • PH
Список алгоритмов

Источник: Русская википедия 2012

Вы можете разместить ссылку на этот материал у себя на сайте, блоге или форуме

HTML-cсылка на публикацию
BB-cсылка на публикацию (для форумов)
Прямая ссылка на публикацию


Похожие статьи
Классы L и NL
Классы L и NL Это статья о классах языков для детерминированной машины Тьюринга. Статья о unix-утилите называется nl. Класс языков L — множество языков, разрешимых на детерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной n. Класс языков NL — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной n. Примеры: Пусть язык — ориентированный граф в котором есть путь от s до t, тогда NL-полные задачи Преобразователь, требующий логарифмической

классы
кл'ассы, -ов (игра)

Классы L и NL
Классы L и NL Это статья о классах языков для детерминированной машины Тьюринга. Статья о unix-утилите называется nl. Класс языков L — множество языков, разрешимых на детерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной n. Класс языков NL — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной n. Примеры: Пусть язык — ориентированный граф в котором есть путь от s до t, тогда NL-полные задачи Преобразователь, требующий логарифмической

Классы
Классы Классы общественные, «... большие группы людей, различающиеся по их месту в исторически определенной системе общественного производства, по их отношению (большей частью закрепленному и оформленному в законах) к средствам производства, по их роли в общественной организации труда, а, следовательно, по способам получения и размерам той доли общественного богатства, которой они располагают. Классы, это такие группы людей, из которых одна может себе присваивать труд другой, благодаря различию их места в определенном укладе

Классы L и NL
Классы L и NL Это статья о классах языков для детерминированной машины Тьюринга. Статья о unix-утилите называется nl. Класс языков L — множество языков, разрешимых на детерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной n. Класс языков NL — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной n. Примеры: Пусть язык — ориентированный граф в котором есть путь от s до t, тогда NL-полные задачи Преобразователь, требующий логарифмической

Искать все статьи, похожие на текущую (Классы L и NL)
Это интересно! Шумилинская (Верхнедонской район)   порово-диффузионный   сверло   очувствоваться   По-кафешантанному   
Универсальная энциклопедия 2012
Карта сайта
Страница создана за 0.012021 сек. Всего документов включено в базу знаний: 5150576