Класс сложности

Набор задач по теории сложности вычислений

Представление взаимосвязей между несколькими важными классами сложности

В теории сложности вычислений класс сложности представляет собой набор вычислительных задач « связанной сложности на основе ресурсов ». ^[1] Двумя наиболее часто анализируемыми ресурсами являются время и память .

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

Изучение отношений между классами сложности является одной из основных областей исследований в теоретической информатике. Часто существуют общие иерархии классов сложности; например, известно, что ряд фундаментальных классов сложности по времени и пространству связаны друг с другом следующим образом: L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE (где ⊆ обозначает отношение подмножества ). Однако многие отношения пока неизвестны; например, одна из самых известных открытых проблем в информатике касается того, равно ли P NP . Отношения между классами часто отвечают на вопросы о фундаментальной природе вычислений. Например, проблема P против NP напрямую связана с вопросами о том, добавляет ли недетерминизм вычислительную мощность компьютерам и можно ли быстро решать проблемы, имеющие решения, которые можно быстро проверить на корректность.

Фон

Классы сложности — это наборы связанных вычислительных задач . Они определяются в терминах вычислительной сложности решения задач, содержащихся в них, относительно конкретных вычислительных ресурсов, таких как время или память. Более формально определение класса сложности состоит из трех вещей: типа вычислительной задачи, модели вычисления и ограниченного вычислительного ресурса. В частности, большинство классов сложности состоят из задач принятия решений , которые могут быть решены машиной Тьюринга с ограниченными временными или пространственными ресурсами. Например, класс сложности P определяется как набор задач принятия решений , которые могут быть решены детерминированной машиной Тьюринга за полиномиальное время .

Вычислительные проблемы

Интуитивно вычислительная задача — это просто вопрос, который может быть решен с помощью алгоритма . Например, «является ли натуральное число простым ?» — это вычислительная задача. Вычислительная задача математически представлена ​​как набор ответов на задачу. В примере с простотой задача (назовем ее ) представлена ​​набором всех натуральных чисел, которые являются простыми: . В теории вычислений эти ответы представлены в виде строк ; например, в примере с простотой натуральные числа могут быть представлены в виде строк битов , которые представляют двоичные числа . По этой причине вычислительные задачи часто синонимично называют языками, поскольку строки битов представляют формальные языки (концепция, заимствованная из лингвистики ); например, утверждение, что задача находится в классе сложности NP , эквивалентно утверждению, что язык находится в NP . ${\displaystyle n}$ ${\displaystyle {\texttt {PRIME}}}$ ${\displaystyle {\texttt {PRIME}}=\{n\in \mathbb {N} |n{\text{ is prime}}\}}$ ${\displaystyle {\texttt {PRIME}}}$ ${\displaystyle {\texttt {PRIME}}}$

Проблемы с принятием решений

Задача принятия решения имеет только два возможных результата: да или нет (альтернативно 1 или 0) на любом входе.

Наиболее часто анализируемыми проблемами в теоретической информатике являются проблемы принятия решений — виды проблем, которые могут быть поставлены как вопросы типа «да-нет» . Например, приведенный выше пример простоты является примером проблемы принятия решений, поскольку она может быть представлена ​​вопросом типа «да-нет» «является ли натуральное число простым ». С точки зрения теории вычислений проблема принятия решений представлена ​​как набор входных строк, на которые компьютер, работающий по правильному алгоритму, ответил бы «да». В примере простоты — это набор строк, представляющих натуральные числа, которые при вводе в компьютер, работающий по алгоритму, который правильно проверяет простоту , алгоритм отвечает «да, это число является простым». Этот формат «да-нет» часто эквивалентно обозначается как «принять-отклонить»; то есть алгоритм «принимает» входную строку, если ответ на проблему принятия решений — «да», и «отклоняет», если ответ — «нет». ${\displaystyle n}$ ${\displaystyle {\texttt {PRIME}}}$

Хотя некоторые проблемы не могут быть легко выражены как проблемы принятия решений, они, тем не менее, охватывают широкий спектр вычислительных проблем. ^[2] Другие типы проблем, в терминах которых определяются определенные классы сложности, включают:

• Проблемы с функциями (например, ФП )
• Проблемы со счетом (например, #P )
• Проблемы оптимизации
• Проблемы с обещаниями (см. раздел «Другие типы проблем»)

Вычислительные модели

Чтобы конкретизировать понятие «компьютер», в теоретической информатике проблемы анализируются в контексте вычислительной модели . Вычислительные модели уточняют понятия вычислительных ресурсов, таких как «время» и «память». В теории вычислительной сложности классы сложности имеют дело с неотъемлемыми требованиями к ресурсам проблем, а не с требованиями к ресурсам, которые зависят от того, как устроен физический компьютер. Например, в реальном мире разным компьютерам может потребоваться разное количество времени и памяти для решения одной и той же задачи из-за того, как они были спроектированы. Предоставляя абстрактное математическое представление компьютеров, вычислительные модели абстрагируются от излишних сложностей реального мира (например, различий в скорости процессора ), которые мешают пониманию фундаментальных принципов.

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

Также возможно использовать аксиомы Блюма для определения классов сложности без ссылки на конкретную вычислительную модель , но этот подход реже используется в теории сложности.

Детерминированные машины Тьюринга

Иллюстрация машины Тьюринга. Буква «B» обозначает пустой символ.

Машина Тьюринга — это математическая модель общей вычислительной машины. Это наиболее часто используемая модель в теории сложности, во многом благодаря тому, что она считается столь же мощной, как и любая другая модель вычислений, и ее легко анализировать математически. Важно то, что считается, что если существует алгоритм, который решает определенную задачу, то существует и машина Тьюринга, которая решает ту же самую задачу (это известно как тезис Чёрча–Тьюринга ); это означает, что считается, что каждый алгоритм может быть представлен как машина Тьюринга.

Механически машина Тьюринга (TM) манипулирует символами (обычно ограниченными битами 0 и 1 для обеспечения интуитивной связи с реальными компьютерами), содержащимися на бесконечно длинной полосе ленты. TM может считывать и записывать по одному за раз с помощью головки ленты. Работа полностью определяется конечным набором элементарных инструкций, таких как «в состоянии 42, если видимый символ равен 0, записать 1; если видимый символ равен 1, перейти в состояние 17; в состоянии 17, если видимый символ равен 0, записать 1 и перейти в состояние 6». Машина Тьюринга начинает работу только с входной строкой на своей ленте и оставляет пустыми все остальное. TM принимает ввод, если она входит в назначенное состояние принятия, и отклоняет ввод, если она входит в состояние отклонения. Детерминированная машина Тьюринга (DTM) является самым базовым типом машины Тьюринга. Она использует фиксированный набор правил для определения своих будущих действий (вот почему она называется « детерминированной »).

Вычислительная задача может быть определена в терминах машины Тьюринга как набор входных строк, которые принимает конкретная машина Тьюринга. Например, проблема простоты из вышеприведенного примера — это набор строк (представляющих натуральные числа), которые принимает машина Тьюринга, выполняющая алгоритм, который правильно проверяет простоту . Говорят, что машина Тьюринга распознает язык (напомним, что «задача» и «язык» в значительной степени являются синонимами в теории вычислимости и сложности), если она принимает все входные данные, которые есть в языке, и говорят, что она решает язык, если она дополнительно отклоняет все входные данные, которые не есть в языке (определенные входные данные могут заставить машину Тьюринга работать вечно, поэтому разрешимость накладывает дополнительное ограничение на распознаваемость , заключающееся в том, что машина Тьюринга должна останавливаться на всех входных данных). Машина Тьюринга, которая «решает» задачу, обычно подразумевает машину, которая решает язык. ${\displaystyle {\texttt {PRIME}}}$

Машины Тьюринга позволяют использовать интуитивные понятия «времени» и «пространства». Временная сложность TM на конкретном входе — это количество элементарных шагов, которые машина Тьюринга предпринимает для достижения состояния принятия или отклонения. Пространственная сложность — это количество ячеек на ее ленте, которые она использует для достижения состояния принятия или отклонения.

Недетерминированные машины Тьюринга

Сравнение детерминированного и недетерминированного вычисления. Если какая-либо ветвь недетерминированного вычисления принимает, то принимает и NTM.

Детерминированная машина Тьюринга (DTM) является вариантом недетерминированной машины Тьюринга (NTM). Интуитивно NTM — это просто обычная машина Тьюринга, которая имеет дополнительную возможность исследовать несколько возможных будущих действий из заданного состояния и «выбирать» ветвь, которая принимает (если таковая принимает). То есть, в то время как DTM должна следовать только одной ветви вычислений, NTM можно представить как дерево вычислений, разветвляющееся на множество возможных вычислительных путей на каждом шаге (см. изображение). Если хотя бы одна ветвь дерева останавливается с условием «принять», то NTM принимает входные данные. Таким образом, NTM можно рассматривать как одновременно исследующую все вычислительные возможности параллельно и выбирающую принимающую ветвь. ^[3] NTM не предназначены для того, чтобы быть физически реализуемыми моделями, они просто теоретически интересные абстрактные машины, которые порождают ряд интересных классов сложности (которые часто имеют физически реализуемые эквивалентные определения).

Временная сложность NTM — это максимальное количество шагов, которые NTM использует в любой ветви своих вычислений. ^[4] Аналогично, пространственная сложность NTM — это максимальное количество ячеек, которые NTM использует в любой ветви своих вычислений.

DTM можно рассматривать как особый случай NTM, которые не используют силу недетерминизма. Следовательно, каждое вычисление, которое может быть выполнено DTM, может быть выполнено и эквивалентным NTM. Также возможно смоделировать любой NTM с помощью DTM (DTM просто вычислит каждую возможную вычислительную ветвь одну за другой). Следовательно, эти два варианта эквивалентны с точки зрения вычислимости. Однако моделирование NTM с помощью DTM часто требует большего времени и/или ресурсов памяти; как будет видно, насколько существенно это замедление для определенных классов вычислительных задач, является важным вопросом в теории вычислительной сложности.

Ограничения ресурсов

Классы сложности группируют вычислительные задачи по их требованиям к ресурсам. Для этого вычислительные задачи дифференцируются по верхним границам максимального количества ресурсов, которые наиболее эффективный алгоритм использует для их решения. Более конкретно, классы сложности связаны со скоростью роста ресурсов, необходимых для решения конкретных вычислительных задач, по мере увеличения размера входных данных. Например, количество времени, необходимое для решения задач в классе сложности P, растет с полиномиальной скоростью по мере увеличения размера входных данных, что сравнительно медленно по сравнению с задачами в экспоненциальном классе сложности EXPTIME (или, точнее, для задач в EXPTIME , которые находятся за пределами P , поскольку ). ${\displaystyle {\mathsf {P}}\subseteq {\mathsf {EXPTIME}}}$

Обратите внимание, что изучение классов сложности направлено в первую очередь на понимание неотъемлемой сложности, необходимой для решения вычислительных задач. Таким образом, теоретики сложности обычно занимаются поиском наименьшего класса сложности, к которому относится задача, и, следовательно, занимаются определением того, к какому классу относится вычислительная задача, используя наиболее эффективный алгоритм. Например, может быть алгоритм, который решает конкретную задачу за экспоненциальное время, но если наиболее эффективный алгоритм для решения этой задачи выполняется за полиномиальное время, то неотъемлемую временную сложность этой задачи лучше описать как полиномиальную.

Временные рамки

Временная сложность алгоритма относительно модели машины Тьюринга — это количество шагов, которое требуется машине Тьюринга для запуска алгоритма на заданном размере входных данных. Формально временная сложность алгоритма, реализованного с помощью машины Тьюринга, определяется как функция , где — максимальное количество шагов, которое требуется для любых входных данных длины . ${\displaystyle M}$ ${\displaystyle t_{M}:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle t_{M}(n)}$ ${\displaystyle M}$ ${\displaystyle n}$

В теории сложности вычислений теоретические специалисты по информатике меньше озабочены конкретными значениями времени выполнения и больше общим классом функций, к которому относится функция временной сложности. Например, является ли функция временной сложности полиномом ? Логарифмической функцией ? Экспоненциальной функцией ? Или другим видом функции?

Границы пространства

Пространственная сложность алгоритма относительно модели машины Тьюринга — это количество ячеек на ленте машины Тьюринга, которые требуются для запуска алгоритма на заданном размере входных данных. Формально пространственная сложность алгоритма, реализованного с помощью машины Тьюринга, определяется как функция , где — максимальное количество ячеек, которое используется на любых входных данных длины . ${\displaystyle M}$ ${\displaystyle s_{M}:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle s_{M}(n)}$ ${\displaystyle M}$ ${\displaystyle n}$

Базовые классы сложности

Основные определения

Классы сложности часто определяются с использованием гранулярных наборов классов сложности, называемых DTIME и NTIME (для временной сложности) и DSPACE и NSPACE (для пространственной сложности). Используя нотацию O big , они определяются следующим образом:

• Класс временной сложности — это множество всех задач, которые решаются с помощью машины Тьюринга, детерминированной по времени. ${\displaystyle {\mathsf {DTIME}}(t(n))}$ ${\displaystyle O(t(n))}$
• Класс временной сложности — это множество всех задач, которые решаются недетерминированной по времени машиной Тьюринга. ${\displaystyle {\mathsf {NTIME}}(t(n))}$ ${\displaystyle O(t(n))}$
• Класс сложности пространства — это множество всех задач, которые решаются с помощью пространственно-детерминированной машины Тьюринга. ${\displaystyle {\mathsf {DSPACE}}(s(n))}$ ${\displaystyle O(s(n))}$
• Класс сложности пространства — это множество всех задач, которые решаются с помощью пространственно недетерминированной машины Тьюринга. ${\displaystyle {\mathsf {NSPACE}}(s(n))}$ ${\displaystyle O(s(n))}$

Классы временной сложности

П и НП

P — это класс задач, которые решаются детерминированной машиной Тьюринга за полиномиальное время , а NP — это класс задач, которые решаются недетерминированной машиной Тьюринга за полиномиальное время. Или более формально,

${\displaystyle {\mathsf {P}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}(n^{k})}$

${\displaystyle {\mathsf {NP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(n^{k})}$

Часто говорят, что P — это класс задач, которые могут быть решены «быстро» или «эффективно» детерминированным компьютером, поскольку временная сложность решения задачи в P увеличивается относительно медленно с размером входных данных.

Важной характеристикой класса NP является то, что его можно эквивалентно определить как класс задач, решения которых проверяются детерминированной машиной Тьюринга за полиномиальное время. То есть язык находится в NP , если существует детерминированная машина Тьюринга с полиномиальным временем, называемая верификатором, которая принимает в качестве входных данных строку и строку сертификата полиномиального размера и принимает , если она находится в языке, и отклоняет, если она не находится в языке. Интуитивно, сертификат действует как доказательство того, что входные данные находятся в языке. Формально: ^[5] ${\displaystyle w}$ ${\displaystyle c}$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle w}$

NP — это класс языков, для которых существует детерминированная машина Тьюринга с полиномиальным временем и полином такой, что для всех , принадлежит тогда и только тогда, когда существует такой , который принимает . ${\displaystyle L}$ ${\displaystyle M}$ ${\displaystyle p}$ ${\displaystyle w\in \{0,1\}^{*}}$ ${\displaystyle w}$ ${\displaystyle L}$ ${\displaystyle c\in \{0,1\}^{p(|w|)}}$ ${\displaystyle M(w,c)}$

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

Проблема P против NP

Хотя может показаться, что существует очевидная разница между классом задач, которые эффективно решаемы, и классом задач, решения которых просто эффективно проверяемы, P и NP на самом деле находятся в центре одной из самых известных нерешенных задач в информатике: проблемы P против NP . Хотя известно, что (интуитивно детерминированные машины Тьюринга являются всего лишь подклассом недетерминированных машин Тьюринга, которые не используют свой недетерминизм; или, согласно определению верификатора, P является классом задач, верификаторы полиномиального времени которых должны получить только пустую строку в качестве своего сертификата), неизвестно, является ли NP строго большим, чем P. Если P = NP , то отсюда следует, что недетерминизм не обеспечивает дополнительной вычислительной мощности по сравнению с детерминизмом в отношении возможности быстрого нахождения решения задачи; то есть возможность исследовать все возможные ветви вычислений обеспечивает не более чем полиномиальное ускорение по сравнению с возможностью исследовать только одну ветвь. Более того, из этого следует, что если существует доказательство для примера проблемы и это доказательство можно быстро проверить на корректность (то есть, если проблема находится в NP ), то также существует алгоритм, который может быстро построить это доказательство (то есть, если проблема находится в P ). ^[6] Однако подавляющее большинство специалистов по информатике считают, что , ^[7] и большинство криптографических схем, используемых сегодня, полагаются на предположение, что . ^[8] ${\displaystyle {\mathsf {P}}\subseteq {\mathsf {NP}}}$ ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$ ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$

EXPTIME и NEXPTIME

EXPTIME (иногда сокращается до EXP ) — это класс задач принятия решений, решаемых детерминированной машиной Тьюринга за экспоненциальное время, а NEXPTIME (иногда сокращается до NEXP ) — это класс задач принятия решений, решаемых недетерминированной машиной Тьюринга за экспоненциальное время. Или более формально,

${\displaystyle {\mathsf {EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}(2^{n^{k}})}$

${\displaystyle {\mathsf {NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})}$

EXPTIME является строгим надмножеством P , а NEXPTIME является строгим надмножеством NP . Кроме того, EXPTIME NEXPTIME . Неизвестно, является ли это правильным, но если P = NP , то EXPTIME должно быть равно NEXPTIME . ${\displaystyle \subseteq }$

Классы сложности пространства

Л и НЛ

Хотя можно определить классы сложности логарифмического времени, это чрезвычайно узкие классы, поскольку сублинейные времена даже не позволяют машине Тьюринга прочитать весь ввод (потому что ). ^{[a] [9]} Однако существует значительное количество задач, которые можно решить в логарифмическом пространстве. Определения этих классов требуют двухленточной машины Тьюринга , чтобы машина могла хранить весь ввод (можно показать, что с точки зрения вычислимости двухленточная машина Тьюринга эквивалентна одноленточной машине Тьюринга). ^[10] В модели двухленточной машины Тьюринга одна лента является входной лентой, которая доступна только для чтения. Другая — рабочая лента, которая позволяет как читать, так и записывать, и является лентой, на которой машина Тьюринга выполняет вычисления. Пространственная сложность машины Тьюринга измеряется как количество ячеек, которые используются на рабочей ленте. ${\displaystyle \log n<n}$

L (иногда удлиняется до LOGSPACE ) затем определяется как класс задач, разрешимых в логарифмическом пространстве на детерминированной машине Тьюринга, а NL (иногда удлиняется до NLOGSPACE ) — это класс задач, разрешимых в логарифмическом пространстве на недетерминированной машине Тьюринга. Или более формально, ^[10]

${\displaystyle {\mathsf {L}}={\mathsf {DSPACE}}(\log n)}$

${\displaystyle {\mathsf {NL}}={\mathsf {NSPACE}}(\log n)}$

Известно, что . Однако неизвестно, является ли какое-либо из этих соотношений правильным. ${\displaystyle {\mathsf {L}}\subseteq {\mathsf {NL}}\subseteq {\mathsf {P}}}$

PSPACE и NPSPACE

Классы сложности PSPACE и NPSPACE являются пространственными аналогами P и NP . То есть, PSPACE — это класс задач, решаемых в полиномиальном пространстве детерминированной машиной Тьюринга, а NPSPACE — это класс задач, решаемых в полиномиальном пространстве недетерминированной машиной Тьюринга. Более формально,

${\displaystyle {\mathsf {PSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(n^{k})}$

${\displaystyle {\mathsf {NPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})}$

Хотя неизвестно, P = NP , теорема Сэвича, как известно, показала, что PSPACE = NPSPACE . Также известно, что , что интуитивно следует из того факта, что, поскольку запись в ячейку на ленте машины Тьюринга определяется как занимающая одну единицу времени, машина Тьюринга, работающая за полиномиальное время, может записывать только в полиномиальное число ячеек. Предполагается, что P строго меньше PSPACE , но это не доказано. ${\displaystyle {\mathsf {P}}\subseteq {\mathsf {PSPACE}}}$

EXPSPACE и NEXPSPACE

Классы сложности EXPSPACE и NEXPSPACE являются пространственными аналогами EXPTIME и NEXPTIME . То есть EXPSPACE — это класс задач, решаемых в экспоненциальном пространстве детерминированной машиной Тьюринга, а NEXPSPACE — это класс задач, решаемых в экспоненциальном пространстве недетерминированной машиной Тьюринга. Или, более формально,

${\displaystyle {\mathsf {EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(2^{n^{k}})}$

${\displaystyle {\mathsf {NEXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})}$

Теорема Сэвича показала, что EXPSPACE = NEXPSPACE . Этот класс чрезвычайно широк: известно, что он является строгим надмножеством PSPACE , NP и P , и считается строгим надмножеством EXPTIME .

Свойства классов сложности

Закрытие

Классы сложности имеют множество свойств замыкания . Например, классы решений могут быть замкнуты относительно отрицания , дизъюнкции , конъюнкции или даже всех булевых операций . Более того, они также могут быть замкнуты относительно множества схем квантификации. P , например, замкнут относительно всех булевых операций и квантификации над областями полиномиального размера. Свойства замыкания могут быть полезны при разделении классов — один из возможных путей разделения двух классов сложности — найти некоторое свойство замыкания, которым обладает один класс, но не обладает другой.

Каждый класс X , который не замкнут относительно отрицания, имеет дополнительный класс co-X , который состоит из дополнительных языков, содержащихся в X (т.е. ). Например, co-NP является одним из важных дополнительных классов сложности и находится в центре нерешенной проблемы, заключающейся в том, является ли co-NP = NP . ${\displaystyle {\textsf {co-X}}=\{L|{\overline {L}}\in {\mathsf {X}}\}}$

Свойства замкнутости являются одной из основных причин, по которым многие классы сложности определены именно так, как они определены. ^[11] Возьмем, например, задачу, которая может быть решена за время (то есть за линейное время), и задачу, которая может быть решена, в лучшем случае, за время. Обе эти задачи находятся в P , однако время выполнения второй растет значительно быстрее, чем время выполнения первой, по мере увеличения размера входных данных. Можно спросить, не лучше ли определить класс «эффективно решаемых» задач, используя некоторую меньшую полиномиальную границу, например , а не все полиномы, что допускает такие большие расхождения. Однако оказывается, что множество всех полиномов является наименьшим классом функций, содержащим линейные функции, который также замкнут относительно сложения, умножения и композиции (например, , который является полиномом, но ). ^[11] Поскольку мы хотели бы, чтобы композиция одного эффективного алгоритма с другим эффективным алгоритмом все еще считалась эффективной, полиномы являются наименьшим классом, который обеспечивает композицию «эффективных алгоритмов». ^[12] (Обратите внимание, что определение P также полезно, поскольку эмпирически почти все проблемы в P , которые практически полезны, на самом деле имеют полиномиальное время выполнения низкого порядка, и почти все проблемы вне P , которые практически полезны, не имеют известных алгоритмов с малым экспоненциальным временем выполнения, т. е. со временем выполнения, где c близко к 1. ^[13] ) ${\displaystyle O(n)}$ ${\displaystyle O(n^{1000})}$ ${\displaystyle O(n^{3})}$ ${\displaystyle O(n^{3})\circ O(n^{2})=O(n^{6})}$ ${\displaystyle O(n^{6})>O(n^{3})}$ ${\displaystyle O(c^{n})}$

Скидки

Многие классы сложности определяются с использованием концепции редукции . Редукция — это преобразование одной задачи в другую, т. е. редукция берет входные данные из одной задачи и преобразует их во входные данные другой задачи. Например, вы можете преобразовать обычное сложение по основанию 10 в сложение по основанию 2, преобразовав и в их запись по основанию 2 (например, 5+7 становится 101+111). Формально задача сводится к задаче , если существует функция такая, что для каждого , тогда и только тогда, когда . ${\displaystyle x+y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle f}$ ${\displaystyle x\in \Sigma ^{*}}$ ${\displaystyle x\in X}$ ${\displaystyle f(x)\in Y}$

Обычно сокращения используются для того, чтобы передать идею о том, что проблема по крайней мере столь же сложна, как и другая проблема. Таким образом, мы, как правило, заинтересованы в использовании сокращения за полиномиальное время, поскольку любая проблема , которая может быть эффективно сведена к другой проблеме, не сложнее, чем . Формально, проблема сводится за полиномиальное время к проблеме , если существует вычислимая за полиномиальное время функция такая, что для всех , тогда и только тогда, когда . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle p}$ ${\displaystyle x\in \Sigma ^{*}}$ ${\displaystyle x\in X}$ ${\displaystyle p(x)\in Y}$

Обратите внимание, что сокращения могут быть определены многими различными способами. Распространенными сокращениями являются сокращения Кука , сокращения Карпа и сокращения Левина , и они могут различаться в зависимости от ограничений ресурсов, например, сокращения полиномиального времени и сокращения логарифмического пространства .

Твёрдость

Сокращение мотивирует концепцию проблемы, которая является сложной для класса сложности. Проблема является сложной для класса проблем C , если каждая проблема в C может быть сведена за полиномиальное время к . Таким образом, ни одна проблема в C не сложнее, чем , поскольку алгоритм для позволяет нам решить любую проблему в C с не более чем полиномиальным замедлением. Особое значение имеет то, что набор проблем, которые являются сложными для NP, называется набором NP-трудных проблем. ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$

Полнота

Если задача сложна для C и также есть в C , то она считается полной для C. Это означает, что она является самой сложной задачей в C (поскольку может быть много задач, которые одинаково сложны, точнее, она настолько же сложна, как и самые сложные задачи в C ). ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$

Особое значение имеет класс NP -полных задач — наиболее сложных задач в NP . Поскольку все задачи в NP могут быть сведены за полиномиальное время к NP -полным задачам, нахождение NP -полной задачи, которая может быть решена за полиномиальное время, означало бы, что P  =  NP .

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

Теорема Сэвича

Теорема Сэвича устанавливает связь между детерминированными и недетерминированными ресурсами пространства. Она показывает, что если недетерминированная машина Тьюринга может решить задачу, используя пространство, то детерминированная машина Тьюринга может решить ту же задачу в пространстве, т. е. в квадрате пространства. Формально теорема Сэвича утверждает, что для любого , ^[14] ${\displaystyle f(n)}$ ${\displaystyle f(n)^{2}}$ ${\displaystyle f(n)>n}$

${\displaystyle {\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(f\left(n\right)^{2}\right).}$

Важными следствиями теоремы Сэвича являются то, что PSPACE = NPSPACE (поскольку квадрат многочлена по-прежнему является многочленом) и EXPSPACE = NEXPSPACE (поскольку квадрат экспоненты по-прежнему является экспонентой).

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

Теоремы иерархии

По определению DTIME следует, что содержится в , если , так как если . Однако это определение не дает никаких указаний на то, является ли это включение строгим. Для требований времени и пространства условия, при которых включение является строгим, задаются теоремами об иерархии времени и пространства соответственно. Они называются теоремами об иерархии, потому что они индуцируют надлежащую иерархию для классов, определенных путем ограничения соответствующих ресурсов. Теоремы об иерархии позволяют делать количественные утверждения о том, насколько больше дополнительного времени или пространства необходимо для увеличения числа решаемых задач. ${\displaystyle {\mathsf {DTIME}}(n^{k_{1}})}$ ${\displaystyle {\mathsf {DTIME}}(n^{k_{2}})}$ ${\displaystyle k_{1}\leq k_{2}}$ ${\displaystyle O(n^{k_{1}})\subseteq O(n^{k_{2}})}$ ${\displaystyle k_{1}\leq k_{2}}$

Теорема об иерархии времени утверждает, что

${\displaystyle {\mathsf {DTIME}}{\big (}f(n){\big )}\subsetneq {\mathsf {DTIME}}{\big (}f(n)\cdot \log ^{2}(f(n)){\big )}}$.

Теорема о пространственной иерархии утверждает, что

${\displaystyle {\mathsf {DSPACE}}{\big (}f(n){\big )}\subsetneq {\mathsf {DSPACE}}{\big (}f(n)\cdot \log(f(n)){\big )}}$.

Теоремы об иерархии времени и пространства формируют основу для большинства результатов разделения классов сложности. Например, теорема об иерархии времени устанавливает, что P строго содержится в EXPTIME , а теорема об иерархии пространства устанавливает, что L строго содержится в PSPACE .

Другие модели вычислений

Хотя детерминированные и недетерминированные машины Тьюринга являются наиболее часто используемыми моделями вычислений, многие классы сложности определяются в терминах других вычислительных моделей. В частности,

• Ряд классов определяются с использованием вероятностных машин Тьюринга , включая классы BPP , PP , RP и ZPP.
• Ряд классов определяются с использованием интерактивных систем доказательств , включая классы IP , MA и AM.
• Ряд классов определяются с использованием булевых схем , включая классы P/poly и их подклассы NC и AC.
• Ряд классов определены с использованием квантовых машин Тьюринга , включая классы BQP и QMA.

Более подробно они описаны ниже.

Рандомизированное вычисление

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

Вероятностная машина Тьюринга похожа на детерминированную машину Тьюринга, за исключением того, что вместо следования одной функции перехода (набору правил для того, как действовать на каждом шаге вычисления) она вероятностно выбирает между несколькими функциями перехода на каждом шаге. Стандартное определение вероятностной машины Тьюринга определяет две функции перехода, так что выбор функции перехода на каждом шаге напоминает подбрасывание монеты. Случайность, вводимая на каждом шаге вычисления, вносит потенциальную возможность ошибки; то есть строки, которые машина Тьюринга должна принимать, в некоторых случаях могут быть отклонены, а строки, которые машина Тьюринга должна отвергать, в некоторых случаях могут быть приняты. В результате классы сложности, основанные на вероятностной машине Тьюринга, определяются в значительной степени вокруг допустимого количества ошибок. Формально они определяются с использованием вероятности ошибки . Говорят, что вероятностная машина Тьюринга распознает язык с вероятностью ошибки, если: ${\displaystyle \epsilon }$ ${\displaystyle M}$ ${\displaystyle L}$ ${\displaystyle \epsilon }$

1. строка в подразумевает, что ${\displaystyle w}$ ${\displaystyle L}$ ${\displaystyle {\text{Pr}}[M{\text{ accepts }}w]\geq 1-\epsilon }$
2. строка не в подразумевает, что ${\displaystyle w}$ ${\displaystyle L}$ ${\displaystyle {\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon }$

Важные классы сложности

Взаимосвязи между фундаментальными вероятностными классами сложности. BQP — вероятностный квантовый класс сложности , описанный в разделе квантовых вычислений.

Основными рандомизированными классами временной сложности являются ZPP , RP , co-RP , BPP и PP .

Самый строгий класс — ZPP (вероятностное полиномиальное время с нулевой ошибкой), класс задач, решаемых за полиномиальное время с помощью вероятностной машины Тьюринга с вероятностью ошибки 0. Интуитивно понятно, что это самый строгий класс вероятностных задач, поскольку он не требует никакой ошибки вообще .

Немного более свободный класс — RP (рандомизированное полиномиальное время), который не поддерживает ошибку для строк, не входящих в язык, но допускает ограниченную ошибку для строк, входящих в язык. Более формально, язык находится в RP , если существует вероятностная машина Тьюринга с полиномиальным временем, такая, что если строки нет в языке, то она всегда отклоняет, а если строки есть в языке, то принимает с вероятностью не менее 1/2. Класс co-RP определяется аналогичным образом, за исключением того, что роли меняются местами: ошибка не допускается для строк в языке, но допускается для строк, не входящих в язык. Взятые вместе, классы RP и co-RP охватывают все проблемы, которые могут быть решены вероятностными машинами Тьюринга с односторонней ошибкой . ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$

Дальнейшее ослабление требований к ошибкам для учета двусторонней ошибки дает класс BPP (bounded-error probabilistic polynomial time), класс задач, решаемых за полиномиальное время вероятностной машиной Тьюринга с вероятностью ошибки менее 1/3 (как для строк в языке, так и для строк вне языка). BPP является наиболее практически значимым из вероятностных классов сложности — задачи в BPP имеют эффективные рандомизированные алгоритмы , которые могут быстро выполняться на реальных компьютерах. BPP также находится в центре важной нерешенной проблемы в информатике о том, является ли P=BPP , что, если это так, означало бы, что случайность не увеличивает вычислительную мощность компьютеров, т. е. любая вероятностная машина Тьюринга может быть смоделирована детерминированной машиной Тьюринга с не более чем полиномиальным замедлением.

Самый широкий класс эффективно решаемых вероятностных задач — это PP (вероятностное полиномиальное время), множество языков, решаемых вероятностной машиной Тьюринга за полиномиальное время с вероятностью ошибки менее 1/2 для всех строк.

ZPP , RP и co-RP являются подмножествами BPP , который в свою очередь является подмножеством PP . Причина этого интуитивно понятна: классы, допускающие нулевую ошибку и только одностороннюю ошибку, содержатся в классе, допускающем двустороннюю ошибку, а PP просто ослабляет вероятность ошибки BPP . ZPP соотносится с RP и co-RP следующим образом: . То есть, ZPP состоит именно из тех проблем, которые есть как в RP, так и в co-RP . Интуитивно это следует из того факта, что RP и co-RP допускают только одностороннюю ошибку: co-RP не допускает ошибку для строк в языке, а RP не допускает ошибку для строк не в языке. Следовательно, если проблема есть и в RP , и в co-RP , то не должно быть ошибки ни для строк как в языке , так и не в нем (т. е. вообще никакой ошибки), что и является определением ZPP . ${\displaystyle {\textsf {ZPP}}={\textsf {RP}}\cap {\textsf {co-RP}}}$

Важные рандомизированные классы сложности пространства включают BPL , RL и RLP .

Интерактивные системы доказательств

Ряд классов сложности определяются с использованием интерактивных систем доказательств . Интерактивные доказательства обобщают определение доказательств класса сложности NP и дают представление о криптографии , аппроксимационных алгоритмах и формальной проверке .

Общее представление протокола интерактивного доказательства

Интерактивные системы доказательств — это абстрактные машины , которые моделируют вычисления как обмен сообщениями между двумя сторонами: доказывающей и проверяющей . Стороны взаимодействуют, обмениваясь сообщениями, и входная строка принимается системой, если проверяющая решает принять входные данные на основе сообщений, которые она получила от доказывающей. Доказывающая имеет неограниченную вычислительную мощность, в то время как проверяющая имеет ограниченную вычислительную мощность (стандартное определение интерактивных систем доказательств определяет проверяющую как полиномиально ограниченную по времени). Однако доказывающая является ненадежной (это препятствует тому, чтобы все языки были тривиально распознаны системой доказательств, заставляя вычислительно неограниченную доказывающую решать, находится ли строка на языке, а затем отправлять надежные «ДА» или «НЕТ» проверяющей), поэтому проверяющая должна провести «допрос» доказывающей, «задавая ей» последовательные раунды вопросов, принимая только в том случае, если она вырабатывает высокую степень уверенности в том, что строка находится на языке. ^[15] ${\displaystyle P}$ ${\displaystyle V}$ ${\displaystyle P}$

Важные классы сложности

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

Оказывается, NP охватывает всю мощь интерактивных систем доказательств с детерминированными (полиномиальными по времени) верификаторами, поскольку можно показать, что для любой системы доказательств с детерминированным верификатором никогда не требуется больше одного раунда обмена сообщениями между доказывающим и верификатором. Интерактивные системы доказательств, которые обеспечивают большую вычислительную мощность по сравнению со стандартными классами сложности, таким образом, требуют вероятностных верификаторов, что означает, что вопросы верификатора к доказывающему вычисляются с использованием вероятностных алгоритмов . Как отмечалось в разделе выше о рандомизированных вычислениях , вероятностные алгоритмы вносят ошибку в систему, поэтому классы сложности, основанные на вероятностных системах доказательств, определяются в терминах вероятности ошибки . ${\displaystyle \epsilon }$

Наиболее общим классом сложности, вытекающим из этой характеристики, является класс IP (интерактивное полиномиальное время), который представляет собой класс всех задач, решаемых интерактивной системой доказательства , где — вероятностное полиномиальное время, а система доказательства удовлетворяет двум свойствам: для языка ${\displaystyle (P,V)}$ ${\displaystyle V}$ ${\displaystyle L\in {\mathsf {IP}}}$

1. (Полнота) строка в подразумевает ${\displaystyle w}$ ${\displaystyle L}$ ${\displaystyle \Pr[V{\text{ accepts }}w{\text{ after interacting with }}P]\geq {\tfrac {2}{3}}}$
2. (Здоровье) строка не в подразумевает ${\displaystyle w}$ ${\displaystyle L}$ ${\displaystyle \Pr[V{\text{ accepts }}w{\text{ after interacting with }}P]\leq {\tfrac {1}{3}}}$

Важной особенностью IP является то, что он равен PSPACE . Другими словами, любая проблема, которая может быть решена с помощью интерактивной системы доказательства с полиномиальным временем, может быть решена и детерминированной машиной Тьюринга с полиномиальными ресурсами пространства, и наоборот.

Модификация протокола для IP создает еще один важный класс сложности: AM (протокол Артура–Мерлина). В определении интерактивных систем доказательств, используемых IP , доказывающий не мог видеть монеты, используемые проверяющим в его вероятностном вычислении — он мог видеть только сообщения, которые проверяющий создавал с помощью этих монет. По этой причине монеты называются частными случайными монетами . Интерактивная система доказательств может быть ограничена таким образом, чтобы монеты, используемые проверяющим, были публичными случайными монетами ; то есть доказывающий мог видеть монеты. Формально AM определяется как класс языков с интерактивным доказательством, в котором проверяющий отправляет случайную строку доказывающему, доказывающий отвечает сообщением, а проверяющий либо принимает, либо отклоняет, применяя детерминированную полиномиальную функцию времени к сообщению от доказывающего. AM можно обобщить до AM [ k ], где k — количество обмененных сообщений (поэтому в обобщенной форме стандартный AM, определенный выше, — это AM [2]). Однако, для всех AM [ k ] = AM [2]. Также верно, что . ${\displaystyle k\geq 2}$ ${\displaystyle {\mathsf {AM}}[k]\subseteq {\mathsf {IP}}[k]}$

Другие классы сложности, определяемые с использованием интерактивных систем доказательства, включают MIP (мультидоказательное интерактивное полиномиальное время) и QIP (квантовое интерактивное полиномиальное время).

Булевы схемы

Пример булевой схемы, вычисляющей булеву функцию , с примерами входных данных , и . Узлы — это вентили И , узлы — это вентили ИЛИ , а узлы — это вентили НЕ . ${\displaystyle f_{C}(x_{1},x_{2},x_{3})=\neg (x_{1}\wedge x_{2})\wedge ((x_{2}\wedge x_{3})\vee \neg x_{3})}$ ${\displaystyle x_{1}=0}$ ${\displaystyle x_{2}=1}$ ${\displaystyle x_{3}=0}$ ${\displaystyle \wedge }$ ${\displaystyle \vee }$ ${\displaystyle \neg }$

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

Формально, булева схема представляет собой направленный ациклический граф , в котором ребра представляют собой провода (которые несут битовые значения 0 и 1), входные биты представлены исходными вершинами (вершинами без входящих ребер), а все неисходные вершины представляют собой логические вентили (обычно вентили И , ИЛИ и НЕ ). Один логический вентиль обозначается как выходной вентиль и представляет собой конец вычисления. Поведение ввода/вывода схемы с входными переменными представлено булевой функцией ; например, на входных битах выходной бит схемы математически представлен как . Говорят, что схема вычисляет булеву функцию . ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle n}$ ${\displaystyle f_{C}:\{0,1\}^{n}\to \{0,1\}}$ ${\displaystyle x_{1},x_{2},...,x_{n}}$ ${\displaystyle b}$ ${\displaystyle b=f_{C}(x_{1},x_{2},...,x_{n})}$ ${\displaystyle C}$ ${\displaystyle f_{C}}$

Любая конкретная схема имеет фиксированное количество входных вершин, поэтому она может действовать только на входах этого размера. Однако языки (формальные представления задач принятия решений ) содержат строки разной длины, поэтому языки не могут быть полностью охвачены одной схемой (это контрастирует с моделью машины Тьюринга, в которой язык полностью описывается одной машиной Тьюринга, которая может действовать на входах любого размера). Таким образом, язык представлен семейством схем . Семейство схем представляет собой бесконечный список схем , где — схема с входными переменными. Говорят, что семейство схем определяет язык , если для каждой строки , находится в языке тогда и только тогда, когда , где — длина . Другими словами, строка размера находится в языке, представленном семейством схем , если схема (схема с тем же количеством входных вершин, что и количество бит в ) оценивается как 1, когда — ее вход. ${\displaystyle (C_{0},C_{1},C_{2},...)}$ ${\displaystyle C_{n}}$ ${\displaystyle n}$ ${\displaystyle L}$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle L}$ ${\displaystyle C_{n}(w)=1}$ ${\displaystyle n}$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle n}$ ${\displaystyle (C_{0},C_{1},C_{2},...)}$ ${\displaystyle C_{n}}$ ${\displaystyle w}$ ${\displaystyle w}$

В то время как классы сложности, определенные с помощью машин Тьюринга, описываются в терминах временной сложности , классы сложности схем определяются в терминах размера схемы — количества вершин в схеме. Размерная сложность семейства схем — это функция , где — размер схемы . Знакомые классы функций естественным образом следуют из этого; например, семейство схем полиномиального размера — это такое, что функция является полиномом . ${\displaystyle (C_{0},C_{1},C_{2},...)}$ ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle f(n)}$ ${\displaystyle C_{n}}$ ${\displaystyle f}$

Важные классы сложности

Класс сложности P/poly — это множество языков, разрешимых семействами схем полиномиального размера. Оказывается, что существует естественная связь между сложностью схемы и временной сложностью. Интуитивно, язык с небольшой временной сложностью (то есть требующий относительно небольшого количества последовательных операций на машине Тьюринга), также имеет небольшую сложность схемы (то есть требующий относительно небольшого количества булевых операций). Формально можно показать, что если язык принадлежит , где — функция , то он имеет сложность схемы . ^[16] Из этого факта непосредственно следует, что . Другими словами, любая задача, которая может быть решена за полиномиальное время детерминированной машиной Тьюринга, также может быть решена семейством схем полиномиального размера. Кроме того, включение является собственным, то есть (например, существуют некоторые неразрешимые задачи , которые принадлежат P/poly ). ${\displaystyle {\mathsf {DTIME}}(t(n))}$ ${\displaystyle t}$ ${\displaystyle t:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle O(t^{2}(n))}$ ${\displaystyle {\mathsf {\color {Blue}P}}\subset {\textsf {P/poly}}}$ ${\displaystyle {\textsf {P}}\subsetneq {\textsf {P/poly}}}$

P/poly имеет ряд свойств, которые делают его весьма полезным при изучении взаимосвязей между классами сложности. В частности, он полезен при исследовании проблем, связанных с P и NP . Например, если в NP есть какой-либо язык , которого нет в P/poly , то . ^[17] P/poly также полезен при исследовании свойств полиномиальной иерархии . Например, если NP ⊆ P/poly , то PH схлопывается до . Полное описание взаимосвязей между P/poly и другими классами сложности доступно в разделе « Важность P/poly ». P/poly также полезен при общем изучении свойств машин Тьюринга , поскольку класс может быть эквивалентно определен как класс языков, распознаваемых полиномиальной машиной Тьюринга с полиномиально ограниченной функцией совета . ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$ ${\displaystyle \Sigma _{2}^{\mathsf {P}}}$

Два подкласса P/poly , которые сами по себе обладают интересными свойствами, — это NC и AC . Эти классы определяются не только с точки зрения размера схемы, но и с точки зрения глубины . Глубина схемы — это длина самого длинного направленного пути от входного узла до выходного узла. Класс NC — это набор языков, которые могут быть решены семействами схем, которые ограничены не только полиномиальным размером, но и полилогарифмической глубиной. Класс AC определяется аналогично NC , однако вентилям разрешено иметь неограниченное объединение по входу (то есть вентили AND и OR могут применяться более чем к двум битам). NC — это примечательный класс, поскольку его можно эквивалентно определить как класс языков, которые имеют эффективные параллельные алгоритмы .

Квантовые вычисления

Классы BQP и QMA , имеющие ключевое значение в квантовой информатике , определяются с использованием квантовых машин Тьюринга .

Другие типы проблем

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

Проблемы с подсчетом

Задача подсчета не только спрашивает, существует ли решение (как в задаче принятия решений ), но и спрашивает, сколько решений существует. ^[18] Например, задача принятия решений спрашивает , имеет ли конкретный граф простой цикл (ответ — просто да/нет); соответствующая задача подсчета (произносится как «острый цикл») спрашивает, сколько простых циклов имеет. ^[19] Таким образом, вывод задачи подсчета — это число, в отличие от вывода для задачи принятия решений, который является простым да/нет (или принять/отклонить, 0/1 или другой эквивалентной схемой). ^[20] ${\displaystyle {\texttt {CYCLE}}}$ ${\displaystyle G}$ ${\displaystyle \#{\texttt {CYCLE}}}$ ${\displaystyle G}$

Таким образом, в то время как проблемы принятия решений математически представлены как формальные языки , проблемы подсчета представлены математически как функции : задача подсчета формализуется как функция, такая что для каждого ввода , — это количество решений. Например, в задаче ввод — это граф (граф, представленный как строка битов ), а — это количество простых циклов в . ${\displaystyle f:\{0,1\}^{*}\to \mathbb {N} }$ ${\displaystyle w\in \{0,1\}^{*}}$ ${\displaystyle f(w)}$ ${\displaystyle \#{\texttt {CYCLE}}}$ ${\displaystyle G\in \{0,1\}^{*}}$ ${\displaystyle f(G)}$ ${\displaystyle G}$

Задачи подсчета возникают в ряде областей, включая статистическую оценку , статистическую физику , проектирование сетей и экономику . ^[21]

Важные классы сложности

#P (произносится как «острый P») — важный класс задач подсчета, которые можно рассматривать как версию NP для подсчета . ^[22] Связь с NP возникает из того факта, что количество решений задачи равно количеству принимающих ветвей в дереве вычислений недетерминированной машины Тьюринга . Таким образом, #P формально определяется следующим образом:

#P — это множество всех функций, таких что существует недетерминированная машина Тьюринга с полиномиальным временем работы, такая что для всех , равно числу принимающих ветвей в дереве вычислений на . ^[22] ${\displaystyle f:\{0,1\}^{*}\to \mathbb {N} }$ ${\displaystyle M}$ ${\displaystyle w\in \{0,1\}^{*}}$ ${\displaystyle f(w)}$ ${\displaystyle M}$ ${\displaystyle w}$

И так же, как NP может быть определена как в терминах недетерминизма, так и в терминах верификатора (т. е. как интерактивная система доказательств ), так и #P может быть эквивалентно определена в терминах верификатора. Напомним, что задача принятия решения находится в NP , если существует проверяемый за полиномиальное время сертификат для данного экземпляра задачи — то есть NP спрашивает, существует ли доказательство членства (сертификат) для входных данных, корректность которого можно проверить за полиномиальное время. Класс #P спрашивает, сколько таких сертификатов существует. ^[22] В этом контексте #P определяется следующим образом:

#P — это набор функций , такой что существует полиномиальная и полиномиальная по времени машина Тьюринга (верификатор), такая что для каждого , . ^[23] Другими словами, равно размеру набора, содержащего все сертификаты полиномиального размера для . ${\displaystyle f:\{0,1\}^{*}\to \mathbb {N} }$ ${\displaystyle p:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle V}$ ${\displaystyle w\in \{0,1\}^{*}}$ ${\displaystyle f(w)={\Big |}{\big \{}c\in \{0,1\}^{p(|w|)}:V(w,c)=1{\big \}}{\Big |}}$ ${\displaystyle f(w)}$ ${\displaystyle w}$

Проблемы с функциями

Задачи подсчета являются подмножеством более широкого класса задач, называемых функциональными задачами . Функциональная задача — это тип задачи, в которой вычисляются значения функции . Формально функциональная задача определяется как отношение между строками произвольного алфавита : ${\displaystyle f:A\to B}$ ${\displaystyle f}$ ${\displaystyle R}$ ${\displaystyle \Sigma }$

${\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}}$

Алгоритм решает, если для каждого ввода, такого, что существует удовлетворяющий , алгоритм выдает один такой . Это просто другой способ сказать, что есть функция , и алгоритм решает для всех . ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle (x,y)\in R}$ ${\displaystyle y}$ ${\displaystyle f}$ ${\displaystyle f(x)}$ ${\displaystyle x\in \Sigma ^{*}}$

Важные классы сложности

Важным классом сложности функций является FP , класс эффективно решаемых функций. ^[23] Более конкретно, FP — это набор функциональных задач, которые могут быть решены детерминированной машиной Тьюринга за полиномиальное время . ^[23] FP можно рассматривать как эквивалент функциональной задачи P . Важно отметить, что FP дает некоторое представление как о задачах подсчета, так и о P против NP . Если #P = FP , то функции, определяющие количество сертификатов для задач в NP, эффективно решаемы. И поскольку вычисление количества сертификатов по крайней мере так же сложно, как определение того, существует ли сертификат, из этого должно следовать, что если #P = FP , то P = NP (неизвестно, выполняется ли это в обратном порядке, т. е. следует ли из P = NP #P = FP ). ^[23]

Так же, как FP является эквивалентом функциональной задачи P , FNP является эквивалентом функциональной задачи NP . Важно, что FP = FNP тогда и только тогда, когда P = NP . ^[24]

Проблемы с обещаниями

Проблемы обещаний являются обобщением проблем принятия решений, в которых входные данные для проблемы гарантированно («обещано») будут из определенного подмножества всех возможных входных данных. Напомним, что в проблеме принятия решений алгоритм для должен действовать (правильно) на каждом . Проблема обещаний ослабляет требование к входным данным на , ограничивая входные данные некоторым подмножеством . ${\displaystyle L\subseteq \{0,1\}^{*}}$ ${\displaystyle M}$ ${\displaystyle L}$ ${\displaystyle w\in \{0,1\}^{*}}$ ${\displaystyle M}$ ${\displaystyle \{0,1\}^{*}}$

В частности, задача обещания определяется как пара непересекающихся множеств , где: ^[25] ${\displaystyle (\Pi _{\text{ACCEPT}},\Pi _{\text{REJECT}})}$

• ${\displaystyle \Pi _{\text{ACCEPT}}\subseteq \{0,1\}^{*}}$представляет собой набор всех принятых входных данных.
• ${\displaystyle \Pi _{\text{REJECT}}\subseteq \{0,1\}^{*}}$это набор всех отклоненных входных данных.

Входными данными для алгоритма для задачи обещания являются , что называется обещанием . Говорят, что строки в удовлетворяют обещанию . ^[25] По определению и должны быть непересекающимися, т.е. . ${\displaystyle M}$ ${\displaystyle (\Pi _{\text{ACCEPT}},\Pi _{\text{REJECT}})}$ ${\displaystyle \Pi _{\text{ACCEPT}}\cup \Pi _{\text{REJECT}}}$ ${\displaystyle \Pi _{\text{ACCEPT}}\cup \Pi _{\text{REJECT}}}$ ${\displaystyle \Pi _{\text{ACCEPT}}}$ ${\displaystyle \Pi _{\text{REJECT}}}$ ${\displaystyle \Pi _{\text{ACCEPT}}\cap \Pi _{\text{REJECT}}=\emptyset }$

В рамках этой формулировки можно увидеть, что проблемы принятия решений являются лишь подмножеством проблем обещаний с тривиальным обещанием . Таким образом, в случае проблем принятия решений проще просто определить проблему как только (с неявным бытием ), что на этой странице обозначается , чтобы подчеркнуть, что это формальный язык . ${\displaystyle \Pi _{\text{ACCEPT}}\cup \Pi _{\text{REJECT}}=\{0,1\}^{*}}$ ${\displaystyle \Pi _{\text{ACCEPT}}}$ ${\displaystyle \Pi _{\text{REJECT}}}$ ${\displaystyle \{0,1\}^{*}/\Pi _{\text{ACCEPT}}}$ ${\displaystyle L}$ ${\displaystyle \Pi _{\text{ACCEPT}}=L}$

Проблемы обещаний позволяют более естественно формулировать многие вычислительные проблемы. Например, вычислительная проблема может быть чем-то вроде «дан планарный граф , определить, является ли...» ^[26] Это часто формулируется как проблема принятия решения, где предполагается, что существует некоторая схема перевода, которая переводит каждую строку в планарный граф. Однако проще определить это как проблему обещаний, в которой входные данные обещают быть планарным графом. ${\displaystyle s\in \{0,1\}^{*}}$

Отношение к классам сложности

Задачи обещаний предоставляют альтернативное определение для стандартных классов сложности задач принятия решений. P , например, можно определить как задачу обещаний: ^[27]

P — это класс задач обещания, которые решаются за детерминированное полиномиальное время. То есть, задача обещания находится в P, если существует алгоритм полиномиального времени такой, что: ${\displaystyle (\Pi _{\text{ACCEPT}},\Pi _{\text{REJECT}})}$ ${\displaystyle M}$

• Для каждого ${\displaystyle x\in \Pi _{\text{ACCEPT}},M(x)=1}$
• Навсегда ${\displaystyle x\in \Pi _{\text{REJECT}},M(x)=0}$

Классы задач принятия решений, то есть классы задач, определяемых как формальные языки, таким образом, естественным образом переводятся в задачи обещаний, где язык в классе просто и неявно . ${\displaystyle L}$ ${\displaystyle L=\Pi _{\text{ACCEPT}}}$ ${\displaystyle \Pi _{\text{REJECT}}}$ ${\displaystyle \{0,1\}^{*}/\Pi _{\text{ACCEPT}}}$

Формулирование многих базовых классов сложности, таких как P , как проблем обещаний дает мало дополнительного понимания их природы. Однако есть некоторые классы сложности, для которых формулирование их как проблем обещаний было полезным для компьютерных ученых. Проблемы обещаний, например, сыграли ключевую роль в изучении SZK (статистического нулевого знания). ^[28]

Сводка отношений между классами сложности

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

Смотрите также

• Список классов сложности

Примечания

1. В то время как логарифмическое время выполнения , т. е. умноженное на константу , позволяет машине Тьюринга считывать входные данные размером , неизменно достигается точка, где . ${\displaystyle c\log n}$ ${\displaystyle \log n}$ ${\displaystyle c}$ ${\displaystyle n<c\log n}$ ${\displaystyle n>c\log n}$

Ссылки

1. Джонсон (1990).
2. Арора и Барак 2009, стр. 28.
3. Сипсер 2006, стр. 48, 150.
4. Сипсер 2006, стр. 255.
5. Ааронсон 2017, стр. 12.
6. Ааронсон 2017, стр. 3.
7. Гасарх 2019.
8. Ааронсон 2017, стр. 4.
9. Сипсер 2006, стр. 320.
10. Sipser 2006, стр. 321.
11. Aaronson 2017, стр. 7.
12. Ааронсон 2017, стр. 5.
13. Ааронсон 2017, стр. 6.
14. Ли 2014.
15. Арора и Барак 2009, стр. 144.
16. Сипсер 2006, стр. 355.
17. Арора и Барак 2009, стр. 286.
18. Фортнау 1997.
19. Арора 2003.
20. Арора и Барак 2009, стр. 342.
21. Арора и Барак 2009, с. 341–342.
22. Барак 2006.
23. Арора и Барак 2009, с. 344.
24. Rich 2008, стр. 689 (510 в предоставленном PDF-файле).
25. Watrous 2006, стр. 1.
26. Гольдрейх 2006, с. 255 (2–3 в предоставленном PDF-файле).
27. Гольдрейх 2006, с. 257 (4 в предоставленном PDF-файле).
28. Гольдрейх 2006, с. 266 (11–12 в предоставленном PDF-файле).

Библиография

• Ааронсон, Скотт (8 января 2017 г.). "P=?NP". Электронный коллоквиум по вычислительной сложности . Институт Вейцмана. Архивировано из оригинала 17 июня 2020 г.
• Arora, Sanjeev ; Barak, Boaz (2009). Computational Complexity: A Modern Approach . Cambridge University Press. Черновик. Архивировано из оригинала 23 февраля 2022 г. ISBN 978-0-521-42426-4.
• Арора, Санджив (весна 2003 г.). «Классы сложности, связанные с подсчетом». Computer Science 522: Computational Complexity Theory . Princeton University. Архивировано из оригинала 21 мая 2022 г.
• Барак, Боаз (весна 2006 г.). "Сложность подсчета" (PDF) . Компьютерные науки 522: Вычислительная сложность . Принстонский университет . Архивировано из оригинала 3 апреля 2021 г.
• Fortnow, Lance (1997). "Подсчет сложности" (PDF) . В Hemaspaandra, Lane A.; Selman, Alan L. (ред.). Теория сложности. Ретроспектива II . Springer. стр. 81–106. ISBN 9780387949734. Архивировано из оригинала (PDF) 18 июня 2022 г.
• Gasarch, William I. (2019). "Guest Column: The Third P =? NP Poll" (PDF) . Университет Мэриленда . Архивировано (PDF) из оригинала 2 ноября 2021 г.
• Goldreich, Oded (2006). "On Promise Problems: A Survey" (PDF) . В Goldreich, Oded; Rosenberg, Arnold L.; Selman, Alen L. (ред.). Теоретическая информатика. Lecture Notes in Computer Science, т. 3895 (PDF) . Lecture Notes in Computer Science. Том 3895. Springer. стр. 254–290. doi :10.1007/11685654_12. ISBN 978-3-540-32881-0. Архивировано (PDF) из оригинала 6 мая 2021 г.
• Джонсон, Дэвид С. (1990). «Каталог классов сложности». Алгоритмы и сложность . Справочник по теоретической информатике. Elsevier. С. 67–161. doi :10.1016/b978-0-444-88071-0.50007-2.
• Ли, Джеймс Р. (22 мая 2014 г.). "Лекция 16" (PDF) . CSE431: Введение в теорию вычислений . Вашингтонский университет . Архивировано (PDF) из оригинала 29 ноября 2021 г. . Получено 5 октября 2022 г. .
• Рич, Элейн (2008). Автоматы, вычислимость и сложность: теория и приложения (PDF) . Prentice Hall . ISBN 978-0132288064. Архивировано (PDF) из оригинала 21 января 2022 г.
• Sipser, Michael (2006). Введение в теорию вычислений (PDF) (2-е изд.). США: Thomson Course Technology. ISBN 0-534-95097-3. Архивировано из оригинала (PDF) 7 февраля 2022 г.
• Watrous, John (11 апреля 2006 г.). "Лекция 22: Квантовая вычислительная сложность" (PDF) . Университет Ватерлоо . Архивировано (PDF) из оригинала 18 июня 2022 г.

Дальнейшее чтение

• «Зоопарк сложности» Архивировано 27 августа 2019 г. на Wayback Machine : огромный список классов сложности, справочник для экспертов.
• Нил Иммерман . "Теория вычислительной сложности". Архивировано из оригинала 2016-04-16.Включает диаграмму, показывающую иерархию классов сложности и то, как они соотносятся друг с другом.
• Майкл Гэри и Дэвид С. Джонсон : Компьютеры и неразрешимость: Руководство по теории NP-полноты. Нью-Йорк: WH Freeman & Co., 1979. Стандартный справочник по NP-полным задачам — важной категории задач, решения которых, по-видимому, требуют непрактично много времени для вычисления.