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

Класс языков 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

Определения Класс P

Формальное определение

Алгоритм отождествляется с детерминированной машиной Тьюринга, которая вычисляет ответ по данному на входную ленту слову из входного алфавита . Временем работы алгоритма при фиксированном входном слове x называется количество рабочих тактов машины Тьюринга от начала до остановки машины. Сложностью функции , вычисляемой некоторой машиной Тьюринга, называется функция , зависящая от длины входного слова и равная максимуму времени работы машины по всем входным словам фиксированной длины:

.

Если для функции f существует машина Тьюринга M такая, что для некоторого числа c и достаточно больших n, то говорят, что она принадлежит классу P, или полиномиальна по времени.

Согласно тезису Черча — Тьюринга, любой мыслимый алгоритм можно реализовать на машине Тьюринга. Для любого языка программирования можно определить класс P подобным образом (заменив в определении машину Тьюринга на реализацию языка программирования). Если компилятор языка, на котором реализован алгоритм, замедляет исполнение алгоритма полиномиально (то есть время выполнения алгоритма на машине Тьюринга меньше некоторого многочлена от времени выполнения его на языке программирования), то определения классов P для этого языка и для машины Тьюринга совпадают. Код на ассемблере допускает преобразование в машину Тьюринга с небольшим полиномиальным замедлением, а поскольку все существующие языки допускают компиляцию в ассемблер (опять же, с полиномиальным замедлением), то определения класса P для машин Тьюринга и для любого существующего языка программирования совпадают.

Более узкое определение

Иногда под классом P имеют в виду более узкий класс функций, а именно класс предикатов (функций ). В таком случае языком L, который распознается данным предикатом, называется множество слов, на которых предикат равен 1. Языками класса P называются языки, для которых существуют распознающие их предикаты класса P. Очевидно, что если языки и лежат в классе P, то и их объединение, пересечение и дополнения также лежат в классе P.

Включения класса P в другие классы

Класс P является одним из самых узких классов сложности. Об этом говорит сайт https://intellect.icu . Алгоритмы, принадлежащие ему, принадлежат также классу NP, классу BPP (как допускающие полиномиальную реализацию с нулевой ошибкой), классу PSPACE (т.к. зона работы на машине Тьюринга всегда меньше времени), классу P/Poly (для доказательства этого факта используется понятие протокола работы машины, который переделывается в булеву схему полиномиального размера).

Уже более 30 лет остается нерешенной задача о равенстве классов P и NP. Если они равны, то любую задачу из класса NP можно решить быстро (за полиномиальное время). Однако научное сообщество склоняется в сторону отрицательного ответа на этот вопрос. Кроме того, не доказана и строгость включения в более широкие классы, например, в PSPACE, но равенство P и PSPACE выглядит на данный момент очень сомнительно.

Примеры задач

Задачи, принадлежащие классу P

Примерами задач из класса P являются целочисленное сложение, умножение, деление, взятие остатка от деления, умножения матриц, выяснение связности графов, сортировка множества из n чисел, нахождение эйлерова цикла на графе из m ребер, обнаружение в тексте длиной n некоторого слова, построение покрывающего дерева минимальной стоимости, линейное программирование и некоторые другие.

Задачи, принадлежность которых классу P неизвестна

Существует много задач, для которых не найдено полиномиального алгоритма, но не доказано, что его не существует. Соответственно, неизвестно, принадлежат ли такие задачи классу P. Вот некоторые из них:

1. Задача коммивояжера (а также все остальные NP-полные задачи). Полиномиальное решение этой задачи равносильно установлению равенства классов P и NP.
2. Разложение числа на простые множители.
3. Дискретное логарифмирование в конечном поле.
4. Задача о скрытой подгруппе с n образующими.
5. Дискретное логарифмирование в аддитивной группе точек на эллиптической кривой.

Практическое значение

Поскольку часто приходится вычислять значения функций на входных данных большого объема, нахождение полиномиальных алгоритмов для вычисления функций является очень важной задачей. Считается, что вычислять функции, не лежащие в классе P, заметно сложнее, чем лежащие. Большинство алгоритмов, лежащих в классе P, имеют сложность, не превосходящую многочлен небольшой степени от размера входных данных. Например, стандартный алгоритм перемножения матриц требует n3 умножений (хотя существуют и более быстрые алгоритмы, например, алгоритм Штрассена). Степень многочлена редко бывает большой. Один из таких случаев — предложенный в 2002 году индийскими математиками тест Агравала — Каяла — Саксены, выясняющий, является ли число n простым, за O(log6n) операций.

В теории алгоритмов классом NP (от англ. non-deterministic polynomial) называют множество задач разрешимости, решение которых возможно проверить на машине Тьюринга за время, не превосходящее значения некоторого многочлена от размера входных данных, при наличии некоторых дополнительных сведений (так называемого сертификата решения).

Эквивалентно класс NP включает задачи, которые можно за полиномиальное время решить на недетерминированной машине Тьюринга.

Задачи, имеющие полиномиальные по времени алгоритмы решения, можно решать с помощью компьютера значительно быстрее, чем путем прямого перебора, время которого экспоненциально. Это обуславливает практическое значение проблемы о равенстве классов P и NP.

Определения

Класс сложности NP определяется для множества языков, то есть множеств слов над конечным алфавитом . Язык L называется принадлежащим классу NP, если существуют двуместный предикат из класса P (то есть вычислимый за полиномиальное время) и константа такие, что для всякого слова x условие «x принадлежит L» равносильно условию «найдется y длины меньше такой, что верно » (где |x| — длина слова x). Слово y называется сертификатом принадлежности x языку L. Таким образом, если у нас есть слово, принадлежащее языку, и еще одно слово-свидетель ограниченной длины (которое бывает трудно найти), то мы быстро сможем удостовериться в том, что x действительно принадлежит L.

Эквивалентное определение можно получить, используя понятие недетерминированной машины Тьюринга (то есть такой машины Тьюринга, у программы которой могут существовать разные строки с одинаковой левой частью). Если машина встретила «развилку», то есть неоднозначность в программе, то дальше возможны разные варианты вычисления. Предикат , который представляет данная недетерминированная машина Тьюринга, считается равным единице, если существует хоть один вариант вычисления, возвращающий 1, и нулю, если все варианты возвращают 0. Если длина вычисления, дающего 1, не превосходит некоторого многочлена от длины x, то предикат называется принадлежащим классу NP. Если у языка существует распознающий его предикат из класса NP, то язык называется принадлежащим классу NP. Это определение эквивалентно приведенному выше: в качестве свидетеля можно взять номера нужных веток при развилках в вычислении. Так как для x принадлежащему языку длина всего пути вычисления не превосходит многочлена от длины x, то и длина свидетеля также будет ограничена многочленом от длины x.

Всякую задачу о принадлежности слова x языку L, лежащую в классе NP, можно решить за экспоненциальное время перебором всех возможных сертификатов длины меньше . Для ее решения на квантовом компьютере можно использовать GSA. В этом случае общее количество всех возможных сертификатов, которые нужно перебрать, можно определить по формуле суммы членов геометрической прогрессии со знаменателем, равным числу символов в алфавите {\displaystyle \Sigma }, и 1-м членом, равным 1:

Поэтому для поиска нужного сертификата методом GSA требуется Q-битов. Сертификат будет найден за время, не превышающее .

Соотношение с другими классам

Класс языков, дополнения которых принадлежат NP, называется классом co-NP, хотя и не доказано, что этот класс отличен от класса NP. Пересечение классов NP и co-NP содержит класс P. В частности, класс NP включает в себя класс P. Однако ничего не известно о строгости этого включения.

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

Класс NP включается в другие, более широкие классы, например, в класс PH. Существуют также открытые вопросы о строгости его включения в другие классы.

Примеры задач класса NP

Можно привести много задач, про которые на сегодняшний день неизвестно, принадлежат ли они P, но известно, что они принадлежат NP. Среди них:

• Задача выполнимости булевых формул: узнать по данной булевой формуле, существует ли набор входящих в нее переменных, обращающий ее в 1. Сертификат — такой набор.
• Задача о клике: по данному графу узнать, есть ли в нем клики (полные подграфы) заданного размера. Сертификат — номера вершин, образующих клику.
• Определение наличия в графе гамильтонова цикла. Сертификат — последовательность вершин, образующих гамильтонов цикл.
• Неоптимизационный вариант задачи о коммивояжере (существует ли маршрут не длиннее, чем заданное значение k) — расширенный и более приближенный к реальности вариант предыдущей задачи. Сертификат - такой маршрут.
• Существование целочисленного решения у заданной системы линейных неравенств. Сертификат — решение.
• Отсутствие у заданного числа делителей таких что . Сертификат — разбиение числа на простые сомножители вместе с их сертификатами простоты.

Среди всех задач класса NP можно выделить «самые сложные» — NP-полные задачи. Если удастся решить любую из них за полиномиальное время, то все задачи класса NP также можно будет решить за полиномиальное время.

Класс PH

Класс сложности PH (от англ. polynomial hierarchy) — объединение всех классов сложности из полиномиальной иерархии:

Таким образом, предикат принадлежит классу PH, если существует такое k, что предикат принадлежит классу . Также говорят, что язык, распознаваемый таким предикатом (то есть множество всех слов, на которых предикат возвращает 1), принадлежит классу PH.

Эквивалентные определения

Логическая характеризация

Класс языков PH в точности совпадает с классом языков, выразимых с помощью логики второго порядка.

Игровая характеризация

Назовем конечной игрой следующую структуру. Имеется дерево, вершины которого помечены именами двух игроков A и B (все вершины одного уровня помечены одним и тем же именем, ходы чередуются), а ребра соответствуют ходам игроков. Пусть дано некоторое начальное слово x — начальная конфигурация игры. Тогда количество уровней в дереве (т.е. количество ходов) равно некоторой функции f от длины x, а каждое ребро помечено словом длины g от длины x (ходом игрока является слово, которым помечено ребро). Имеется предикат от начальной конфигурации и последовательности ходов игроков, который определяет, кто выиграл (если он равен 1, то выиграл первый игрок). Поскольку игра конечна, то выигрышная стратегия всегда существует либо у первого игрока, либо у второго. Назовем игру распознающей язык L, если для каждого слова x из L у игрока A есть выигрышная стратегия.

Класс PH является классом всех языков, распознаваемых играми, такими, что f равна константе (т.е. количество ходов в игре фиксировано и не зависит от длины входного слова), а g является многочленом от длины x (таким образом, из каждой вершины дерева, кроме последней, исходит по ребер, где — этот многочлен).

Замкнутость

В отличие от составляющих класс PH классов полиномиальной иерархии, про PH доподлинно известно, что он замкнут относительно пересечения, объединения и дополнения языков. Это означает, что если языки и принадлежат PH, то языки , и принадлежат PH.

Для доказательства достаточно предъявить игры, распознающие эти комбинации языков, если имеются игры, распознающие и . Для дополнения передадим право первого хода другому игроку и в качестве предиката выигрыша возьмем . Для пересечения возьмем две игры, распознающие и , такими, что количество ходов в них одинаковое, а вторую начинает не тот игрок, который делает последний ход в первой. После этого в каждую концевую вершину первой игры добавим вторую игру, а в качестве предиката выигрыша возьмем , где и — разбиение всей последовательности ходов на две: часть, соответствующая первой игре, и часть, соответствующая второй. Для объединения возьмем игры, распознающие и , с одинаковым количеством ходов и одинаковым первым игроком. Создадим новую вершину, соответствующую другому игроку, и прицепим к ней одно дерево первой игры (над этим ребром напишем слово 00...0) и оставшиеся ребер второй игры. Первое слово игры обозначим z, а остальную часть последовательности слов — , а в качестве предиката выигрыша возьмем .

Отношения с другими классами

По определению, в класс PH включены все классы полиномиальной иерархии, в том числе P и NP. Кроме того, он содержит вероятностные классы, такие как класс BPP (т.к. BPP содержится в классе ). Сам класс PH включен в класс PSPACE и класс P^PP (класс задач, которые решаются за полиномиальное время на машине Тьюринга с доступом к оракулу класса PP).

Открытые проблемы

Установлено, что P = NP, тогда и только тогда, когда P = PH. Это утверждение может облегчить доказательство того, что P ≠ NP (если это так), поскольку нужно будет лишь отделить P от более общего класса, чем NP.

Примерное положение BQP на карте классов NP, P, PSPACE.

В теории алгоритмов классом сложности BQP (от англ. bounded error quantum polynomial time) называется класс проблем разрешимости, которые могут быть решены квантовым компьютером за полиномиальное время (время работы над задачей полиномиально зависит от размера входных данных), обеспечив при этом вероятность получения верного ответа как минимум 2/3 для любого входа. Является квантовым аналогом класса BPP.

Другими словами, задача относится к классу BQP, если существует квантовый алгоритм (алгоритм для квантового компьютера), решающий данную проблему с высокой вероятностью и работающий гарантированно не более чем за полиномиальное время. Для произвольного запуска алгоритма вероятность получения неверного ответа должна быть не более 1/3.

Важные представители

Интерес к квантовым вычислениям и компьютерам вызван некоторыми задачами, находящимся в классе BQP, но принадлежность которых к классу P неизвестна:

• Факторизация чисел — алгоритм Шора
• Дискретный логарифм
• Моделирование квантовых систем с несколькими частицами (Задача Фейнмана, иногда также универсальный квантовый симулятор)

Взаимоотношения с другими классами

Класс NC