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

Комплекс задач теории сложности вычислений

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

В теории сложности вычислений класс сложности представляет собой набор вычислительных задач « связанной сложности , основанной на ресурсах ». ^[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] Другие типы задач, в терминах которых определены определенные классы сложности, включают функциональные проблемы (например, FP ), проблемы подсчета (например, #P ), проблемы оптимизации и проблемы обещаний (см. раздел «Другие типы проблем»).

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

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

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

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

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

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

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

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

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

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

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

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

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

Временная сложность 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 (для пространственной сложности). Используя обозначение big O , они определяются следующим образом:

• Класс временной сложности — это набор всех задач, которые решает детерминированная по времени машина Тьюринга. ${\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 — это класс задач, верификаторам которых полиномиальное время нужно только получить пустая строка в качестве их сертификата), неизвестно, строго ли NP больше , чем P. Если P = NP , то отсюда следует, что недетерминизм не обеспечивает никакой дополнительной вычислительной мощности по сравнению с детерминизмом в отношении способности быстро найти решение проблемы; то есть возможность исследовать все возможные ветви вычислений обеспечивает максимум полиномиальное ускорение по сравнению с возможностью исследовать только одну ветвь. Более того, из этого следует, что если существует доказательство для экземпляра проблемы и это доказательство можно быстро проверить на корректность (то есть, если проблема находится в NP ), то также существует алгоритм, который может быстро построить это доказательство ( то есть проблема в P ). ^[6] Однако подавляющее большинство ученых-компьютерщиков считают, что P NP , ^[7] и большинство криптографических схем, используемых сегодня, основаны на предположении, что P NP . ^[8] ${\displaystyle \subseteq }$ ${\displaystyle \neq }$ ${\displaystyle \neq }$

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 , что интуитивно следует из того факта, что, поскольку запись в ячейку на ленте машины Тьюринга определяется как занимающая одну единицу времени, машина Тьюринга, работающая за полиномиальное время, может записывать только в полиномиальное количество ячеек. Есть подозрение, что P строго меньше PSPACE , но это не доказано. ${\displaystyle \subseteq }$

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-X = X ). co-NP , например, является одним из важных дополнительных классов сложности и находится в центре нерешенной проблемы о том, является ли co-NP = NP . ${\displaystyle \{L|{\overline {L}}\in }$ ${\displaystyle \}}$

Свойства замыкания — одна из ключевых причин, по которой многие классы сложности определяются именно так, как они есть. ^[11] Возьмем, к примеру, задачу, которую можно решить за время (то есть за линейное время), и ту, которую можно решить, в лучшем случае, за время. Обе эти проблемы находятся в P , однако время выполнения второй растет значительно быстрее, чем время выполнения первой, по мере увеличения размера входных данных. Можно задаться вопросом, не лучше ли определить класс «эффективно решаемых» задач, используя некоторую меньшую полиномиальную оценку, например , а не все полиномы, которые допускают такие большие расхождения. Однако оказывается, что множество всех полиномов представляет собой наименьший класс функций, содержащий линейные функции, замкнутый также относительно сложения, умножения и композиции (например, , который является полиномом, но ). ^[11] Поскольку мы хотели бы, чтобы сочетание одного эффективного алгоритма с другим эффективным алгоритмом по-прежнему считалось эффективным, полиномы представляют собой наименьший класс, который обеспечивает композицию «эффективных алгоритмов». ^[12] (Обратите внимание, что определение P также полезно, потому что эмпирически почти все проблемы в P , которые практически полезны, на самом деле имеют полиномиальное время выполнения низкого порядка, и почти все проблемы за пределами P , которые практически полезны, не имеют никакого известные алгоритмы с малым экспоненциальным временем выполнения, т.е. со временем выполнения, близким к 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})}$ ${\displaystyle c}$

Скидки

Многие классы сложности определяются с использованием концепции сокращения . Редукция — это преобразование одной проблемы в другую, т. е. редукция берет входные данные одной проблемы и преобразует их во входные данные другой проблемы. Например, вы можете свести обычное сложение по основанию 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 следует, что оно содержится в if , поскольку if . Однако это определение не дает никаких указаний на то, является ли это включение строгим. Для требований времени и пространства условия, при которых включение является строгим, задаются теоремами об иерархии времени и пространства соответственно. Их называют теоремами об иерархии, поскольку они создают правильную иерархию классов, определенных путем ограничения соответствующих ресурсов. Теоремы об иерархии позволяют делать количественные утверждения о том, сколько еще дополнительного времени или пространства необходимо, чтобы увеличить количество проблем, которые можно решить. ${\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. строка in подразумевает, что ${\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 (вероятностное полиномиальное время с ограниченной ошибкой), класс проблем, решаемых за полиномиальное время с помощью вероятностной машины Тьюринга с вероятностью ошибки менее 1/3 (для обеих строк на языке и не на языке). BPP является наиболее практически значимым из классов вероятностной сложности: задачи BPP имеют эффективные рандомизированные алгоритмы , которые можно быстро запускать на реальных компьютерах. BPP также находится в центре важной нерешенной проблемы в информатике о том, является ли P=BPP , что, если это правда, означало бы, что случайность не увеличивает вычислительную мощность компьютеров, т.е. любая вероятностная машина Тьюринга может быть смоделирована детерминированной машиной Тьюринга с максимум полиномиальное замедление.

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

ZPP , RP и co-RP — это подмножества BPP , который, в свою очередь, является подмножеством PP . Причина этого интуитивно понятна: все классы, допускающие нулевую ошибку и только одностороннюю ошибку, содержатся в классе, допускающем двустороннюю ошибку, а PP просто снижает вероятность ошибки BPP . ЗПП относится к РП и ко-РП следующим образом: . То есть ЗПП состоит именно из тех задач, которые есть и в РП , и в ко-РП . Интуитивно это следует из того, что 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 , однако вентилям разрешено иметь неограниченное разветвление (то есть вентили И и ИЛИ могут применяться к более чем двум битам). 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 = ФП ). ^[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 }$

В рамках этой формулировки можно увидеть, что проблемы принятия решений — это всего лишь подмножество проблем с обещанием с тривиальным обещанием . Таким образом, в случае проблем с решением проще просто определить проблему как only (с неявным выражением ), которое на этой странице обозначается , чтобы подчеркнуть, что это формальный язык . ${\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. Ааронсон 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. Рич 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 года.
• Арора, Санджив ; Барак, Вооз (2009). Вычислительная сложность: современный подход . Издательство Кембриджского университета. Черновик. Архивировано из оригинала 23 февраля 2022 года. ISBN. 978-0-521-42426-4.
• Арора, Санджив (весна 2003 г.). «Классы сложности, связанные со счетом». Информатика 522: Теория сложности вычислений . Университет Принстон. Архивировано из оригинала 21 мая 2022 года.
• Барак, Вооз (весна 2006 г.). «Сложность подсчета» (PDF) . Информатика 522: Сложность вычислений . Университет Принстон . Архивировано из оригинала 3 апреля 2021 года.
• Фортнау, Лэнс (1997). «Подсчет сложности» (PDF) . В Хемаспаандре, переулок А.; Селман, Алан Л. (ред.). Ретроспектива теории сложности II . Спрингер. стр. 81–106. ISBN 9780387949734. Архивировано из оригинала (PDF) 18 июня 2022 г.
• Гасарч, Уильям И. (2019). «Колонка гостей: третий опрос P =? NP» (PDF) . Университет Мэриленда . Архивировано (PDF) из оригинала 2 ноября 2021 г.
• Гольдрейх, Одед (2006). «О проблемах с обещаниями: обзор» (PDF) . В Гольдрайхе, Одед; Розенберг, Арнольд Л.; Селман, Ален Л. (ред.). Теоретическая информатика. Конспекты лекций по информатике, том 3895 (PDF) . Конспекты лекций по информатике. Том. 3895. Спрингер. стр. 254–290. дои : 10.1007/11685654_12. ISBN 978-3-540-32881-0. Архивировано (PDF) из оригинала 6 мая 2021 г.
• Джонсон, Дэвид С. (1990). «Каталог классов сложности». Алгоритмы и сложность . Справочник по теоретической информатике. Эльзевир. стр. 67–161. дои : 10.1016/b978-0-444-88071-0.50007-2.
• Ли, Джеймс Р. (22 мая 2014 г.). «Лекция 16» (PDF) . CSE431: Введение в теорию вычислений . Университет Вашингтона . Архивировано (PDF) из оригинала 29 ноября 2021 г. Проверено 5 октября 2022 г.
• Рич, Элейн (2008). Автоматы, вычислимость и сложность: теория и приложения (PDF) . Прентис Холл . ISBN 978-0132288064. Архивировано (PDF) из оригинала 21 января 2022 г.
• Сипсер, Майкл (2006). Введение в теорию вычислений (PDF) (2-е изд.). США: Курс технологии Томсона. ISBN 0-534-95097-3. Архивировано из оригинала (PDF) 7 февраля 2022 г.
• Уотрус, Джон (11 апреля 2006 г.). «Лекция 22: Сложность квантовых вычислений» (PDF) . Университет Ватерлоо . Архивировано (PDF) из оригинала 18 июня 2022 г.

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

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