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

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

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

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

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

Предыстория

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

Вычислительные задачи

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

Проблемы с решением

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

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

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

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

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

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

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

Детерминированные

Основная статья: Машина Тьюринга

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

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

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

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

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

машины

Основная статья: Недетерминированная машина Тьюринга

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

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

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

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

Границы ресурсов

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

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

Сроки

Основная статья: Временная сложность

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

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

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

Основная статья: Пространственная сложность

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

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

См. также: Список классов сложности.

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

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

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

временной

Основная статья: Временная сложность

П и НП

Основные статьи: P (сложность) и NP (сложность)

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

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

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

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

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

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

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

P

Хотя может показаться, что существует очевидная разница между классом проблем, которые эффективно решаемы, и классом проблем, решения которых можно просто эффективно проверить, P и NP на самом деле находятся в центре одной из самых известных нерешенных проблем в информатике: P и NP . проблема Хотя известно, что П. $\subseteq$NP (интуитивно, детерминированные машины Тьюринга — это просто подкласс недетерминированных машин Тьюринга, которые не используют свой недетерминизм; или, согласно определению верификатора, P — это класс задач, верификаторам которых с полиномиальным временем достаточно получить только пустую строку в качестве сертификата ), неизвестно, строго ли NP больше P . Если P = NP , то отсюда следует, что недетерминизм не обеспечивает никакой дополнительной вычислительной мощности по сравнению с детерминизмом в отношении способности быстро найти решение проблемы; то есть возможность исследовать все возможные ветви вычислений обеспечивает максимум полиномиальное ускорение по сравнению с возможностью исследовать только одну ветвь. Более того, из этого следовало бы, что если существует доказательство для экземпляра проблемы и это доказательство можно быстро проверить на корректность (то есть, если проблема находится в NP ), то также существует алгоритм, который может быстро построить это доказательство ( то есть проблема в P ). Однако подавляющее большинство ученых-компьютерщиков считают, что P $\neq$Э.Г. , и большинство используемых сегодня криптографических схем основаны на предположении, что P $\neq$Э.Г. ​

EXPTIME и NEXPTIME

Основные статьи: EXPTIME и NEXPTIME

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

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

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

EXPTIME — это строгий расширенный набор P , а NEXPTIME — строгий расширенный набор NP . Кроме того, EXPTIME $\subseteq$СЛЕДУЮЩИЙ ВРЕМЯ . Неизвестно, правильно ли это, но если P = NP , то EXPTIME должно равняться NEXPTIME .

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

Основная статья: Пространственная сложность

Л и НЛ

Основные статьи: L (сложность) и NL (сложность)

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

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

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

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

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

PSPACE и NPSPACE

Основная статья: PSPACE (сложность)

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

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

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

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

EXPSPACE и NEXPSPACE

Основная статья: EXPSPACE

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

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

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

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

Сокращения

См. также: Сокращение (сложность)

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

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

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

Твердость

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

Полнота

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

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

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

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

Основная статья: теорема Савича

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

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

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

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

Теоремы

Основные статьи: Теорема об иерархии времени и теорема об иерархии пространства.

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

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

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

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

${\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.

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

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

Основная статья: Рандомизированные вычисления

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

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

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

классы

Отношения между фундаментальными классами вероятностной сложности. BQP — это вероятностный класс квантовой сложности , описанный в разделе «Квантовые вычисления».

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

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

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

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

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

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

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

доказательств

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

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

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

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

классы

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

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

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

1. (Полнота) строка $w$ в $L$ подразумевает $\Pr[V{\text{ accepts }}w{\text{ after interacting with }}P]\geq {\tfrac {2}{3}}$
2. (Здоровье) строка $w$ не в $L$ подразумевает $\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, определенный выше, равен АМ [2]). Однако дело обстоит так, что для всех $k\geq 2$, АМ [ к ]= АМ [2]. Это также тот случай, когда ${\mathsf {AM}}[k]\subseteq {\mathsf {IP}}[k]$.

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

Булевы схемы

Основная статья: Сложность схемы

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

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

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

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

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

классы

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

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

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

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

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

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

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

Задачи со счетом

Основная статья: Задача на счет (сложность)

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

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

Проблемы подсчета возникают в ряде областей, включая статистическую оценку , статистическую физику , проектирование сетей и экономику .

классы

Основная статья: ♯П

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

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

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

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

Функциональные проблемы

Основная статья: Функциональная проблема

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

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

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

классы

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

Точно так же, как FP является функциональной проблемой, эквивалентной P , FNP является функциональной проблемой, эквивалентной NP . Важно отметить, что FP = FNP тогда и только тогда, когда P = NP .

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

Основная статья: Проблема с обещаниями

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

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

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

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

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

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

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

Проблемы обещаний предоставляют альтернативное определение стандартных классов сложности проблем принятия решений. P , например, можно определить как проблему обещаний:

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

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

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

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

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

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

		Проблема решения
Тип 0 (рекурсивно перечисляемый)				Неразрешимый
разрешимый
EXPSPACE
СЛЕДУЮЩЕЕ ВРЕМЯ
ВРЕМЯ ЭКСПРЕСС
PSPACE
Тип 1 (контекстно-зависимый)
		со-НП	Министерство национальной обороны		НАПРИМЕР
			БПП
		п
	Северная Каролина
Тип 2 (контекстно-свободный)
Тип 3 (обычный)

См. также

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

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

• Ааронсон, Скотт (8 января 2017 г.). "П=?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-полным проблемам — важной категории проблем, для решения которых требуется непрактично много времени.