Класс сложности - Complexity class

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

В теория сложности вычислений, а класс сложности это набор из вычислительные проблемы связанных ресурсов сложность. Два наиболее часто анализируемых ресурса: время и объем памяти.

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

Изучение взаимоотношений между классами сложности - важная область исследований в теоретической информатике. Часто существуют общие иерархии классов сложности; например, известно, что ряд фундаментальных классов временной и пространственной сложности связаны друг с другом следующим образом: NL${ displaystyle substeq}$п${ displaystyle substeq}$НП${ displaystyle substeq}$PSPACE${ displaystyle substeq}$EXPTIME${ displaystyle substeq}$EXPSPACE (куда ${ displaystyle substeq}$ обозначает подмножество ). Однако многие отношения еще не известны; например, один из самых известных открытые проблемы в информатике касается того, п равно НП. Отношения между классами часто отвечают на вопросы о фундаментальной природе вычислений. В п против НП проблема, например, напрямую связана с вопросами о том, недетерминизм добавляет вычислительную мощность компьютерам и позволяет быстро решать проблемы, имеющие решение, правильность которого можно быстро проверить.

Фон

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Границы времени

В временная сложность алгоритма по отношению к модели машины Тьюринга - это количество шагов, которое требуется машине Тьюринга для выполнения алгоритма с заданным размером входных данных. Формально временная сложность алгоритма, реализованного на машине Тьюринга ${ displaystyle M}$ определяется как функция ${ displaystyle t_ {M}: mathbb {N} to mathbb {N}}$, куда ${ displaystyle t_ {M} (п)}$ это максимальное количество шагов, которое ${ displaystyle M}$ принимает любой ввод длины ${ displaystyle n}$. Например, скажем, что входы в ${ displaystyle M}$ являются двоичными числами. Тогда есть, например, четыре входа размера два: 00, 01, 10 и 11. Скажите, что выполняется ${ displaystyle M}$ 00 - десять шагов, 01 - двенадцать шагов, 10 - восемь шагов и 11 - пятнадцать шагов. Время выполнения ${ displaystyle t_ {M} (2)}$ это максимальное из этих четырех значений времени работы: ${ displaystyle t_ {M} (2) = 15}$.

Однако классы сложности меньше связаны с конкретными значениями времени выполнения и больше с общим классом функций, в которые попадает функция временной сложности. Например, сложность времени a многочлен ? А логарифмическая функция ? An экспоненциальная функция ? Или другая функция? Поскольку функции сложности точного времени часто являются сложными выражениями, они упрощаются с помощью нотация большой O. Это приводит к самым основным наборам классов временной сложности: DTIME и NTIME. Они определены следующим образом:

• Класс временной сложности ${ Displaystyle { mathsf {DTIME}} (т (п))}$ представляет собой совокупность всех проблем, которые решаются ${ Displaystyle О (т (п))}$ детерминированная по времени машина Тьюринга.
• Класс временной сложности ${ Displaystyle { mathsf {NTIME}} (т (п))}$ представляет собой совокупность всех задач, которые решаются ${ Displaystyle О (т (п))}$ недетерминированная по времени машина Тьюринга.

Например, если проблема ${ displaystyle X}$ можно решить с помощью алгоритма, работающего во времени ${ Displaystyle т (п) = 8n ^ {3} + 2n + 4}$ тогда это в DTIME${ Displaystyle (п ^ {3})}$ поскольку ${ displaystyle t (n) = 8n ^ {3} + 2n + 4 = O (n ^ {3})}$. Обратите внимание, что при большой нотации O также верно, что ${ displaystyle 8n ^ {3} + 2n + 4 = O (n ^ {4})}$, ${ displaystyle 8n ^ {3} + 2n + 4 = O (n ^ {5})}$, и так далее. Это означает, что DTIME классы, как правило, не исключают друг друга, а образуют иерархию: DTIME${ Displaystyle (п ^ {3}) substeq}$DTIME${ Displaystyle (п ^ {4}) substeq}$DTIME${ Displaystyle (п ^ {5}) substeq cdots}$. Эта иерархическая природа часто встречается среди классов сложности.

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

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

Самые основные классы космической сложности определяются следующим образом:

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

Классы базовой сложности

ВСЕ это класс всех проблемы решения. Многие важные классы сложности определяются ограничением время или же Космос используется алгоритмом. Некоторые важные классы сложности, определенные таким образом, объясняются ниже.

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

Напомним, что класс временной сложности ${ Displaystyle { mathsf {DTIME}} (т (п))}$ представляет собой совокупность всех задач, которые решаются ${ Displaystyle О (т (п))}$ детерминированная по времени машина Тьюринга и ${ Displaystyle { mathsf {NTIME}} (т (п))}$ представляет собой совокупность всех проблем, которые решаются ${ Displaystyle О (т (п))}$ недетерминированная по времени машина Тьюринга. Классы временной сложности часто формально определяются в терминах этих двух классов.

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})}$

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

Важная особенность класса НП состоит в том, что его можно эквивалентно определить как класс проблем, решения которых проверяемый детерминированной машиной Тьюринга за полиномиальное время. То есть язык в НП если существует детерминированный машина Тьюринга с полиномиальным временем, называемая верификатором, которая принимает на входе строку ${ displaystyle w}$ и а свидетельство нить ${ displaystyle c}$, и принимает ${ displaystyle w}$ если ${ displaystyle w}$ на языке и отвергает ${ displaystyle w}$ если ${ displaystyle w}$ не на языке. Интуитивно сертификат действует как доказательство что вход ${ displaystyle w}$ находится на языке. Эта эквивалентность не только подчеркивает фундаментальную связь между недетерминизм и проверяемость решения, но также предоставляет полезный метод для доказательства того, что язык НП- просто определить подходящий сертификат и показать, что его можно проверить за полиномиальное время.

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

EXPTIME и NEXPTIME

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

${ 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 является строгим надмножеством п и NEXPTIME является строгим надмножеством НП. Далее, EXPTIME${ displaystyle substeq}$NEXPTIME. Неизвестно, правильно ли это, но если п=НП тогда EXPTIME должен равняться NEXPTIME.

Классы космической сложности

Напомним, что класс сложности пространства ${ Displaystyle { mathsf {DSPACE}} (s (п))}$ представляет собой совокупность всех задач, которые решаются ${ Displaystyle О (s (п))}$ пространственно детерминированная машина Тьюринга и ${ displaystyle { mathsf {NSPACE}} (s (n))}$ представляет собой совокупность всех задач, которые решаются ${ Displaystyle О (s (п))}$ пространственная недетерминированная машина Тьюринга. Классы космической сложности часто формально определяются в терминах этих двух классов.

L и NL

Пока можно определить логарифмический классы временной сложности, оказывается, что это чрезвычайно узкие классы, поскольку сублинейные времена даже не позволяют машине Тьюринга читать весь ввод (в данном случае, потому что ${ Displaystyle журнал п <п}$).^[7] Однако есть значимое количество проблем, которые можно решить в логарифмическом пространстве. Определения этих классов требуют двухленточная машина Тьюринга чтобы машина могла хранить весь ввод (можно показать, что с точки зрения вычислимость двухленточная машина Тьюринга эквивалентна одинарной машине Тьюринга).^[8] В двухленточной модели машины Тьюринга одна лента является входной лентой, которая предназначена только для чтения. Другая - это рабочая лента, которая позволяет читать и писать, и является лентой, на которой машина Тьюринга выполняет вычисления. Пространственная сложность машины Тьюринга измеряется количеством ячеек, используемых на рабочей ленте.

L затем определяется как класс задач, разрешимых в логарифмическом пространстве на детерминированной машине Тьюринга, и NL - класс задач, разрешимых в логарифмическом пространстве на недетерминированной машине Тьюринга. Или более формально,^[9]

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

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

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

PSPACE и NPSPACE

Классы сложности PSPACE и NPSPACE являются космическими аналогами п и НП. То есть, 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})}$

Пока не известно, п=НП, Теорема савича лихо показал, что PSPACE=NPSPACE. Также известно, что п${ displaystyle substeq}$PSPACE. Это интуитивно следует из того факта, что, поскольку запись в ячейку на ленте машины Тьюринга определяется как выполнение одной единицы времени, то, если эта машина Тьюринга работает в полиномиальное время, она может записывать только в полиномиальное количество ячеек. Есть подозрение, что это подмножество является правильным, но это не было доказано.

EXPSPACE и NEXPSPACE

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

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

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

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

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

Закрытие

Классы сложности имеют множество закрытие характеристики. Например, классы принятия решений могут быть закрыты под отрицание, дизъюнкция, соединение, или даже под всеми Логические операции. Более того, они также могут быть закрыты в рамках различных схем количественной оценки. п, например, закрывается для всех логических операций и при количественной оценке для областей полиномиального размера (хотя, вероятно, не закрывается для областей экспоненциального размера). Свойства замыкания могут быть полезны при разделении классов - один из возможных путей разделения двух классов сложности - найти какое-то свойство замыкания, которым обладает один, а не другой.

Каждый класс Икс который не закрывается при отрицании, имеет класс дополнения co-X, который состоит из дополнений языков, содержащихся в Икс. Точно так же можно определить логическое закрытие класса и так далее; Однако это делается реже.

Свойства замыкания - одна из ключевых причин, по которой многие классы сложности определены таким образом, как они есть.^[10] Возьмем, к примеру, проблему, которую можно решить в ${ Displaystyle т (п) = п}$ время (то есть в линейном времени) и тот, который может быть решен в лучшем случае за ${ Displaystyle т (п) = п ^ {1000}}$ время. Обе эти проблемы находятся в п, однако время выполнения второго растет значительно быстрее, чем время выполнения первого, по мере увеличения размера ввода. Кто-то может спросить, не лучше ли определять класс «эффективно решаемых» проблем, используя меньшую полиномиальную оценку, например ${ Displaystyle п ^ {2}}$, а не все полиномы, что допускает такие большие расхождения. Однако оказывается, что полиномы - это наименьший класс функций, содержащий линейные функции, замкнутые относительно сложения, умножения и композиции.^[10] Это означает, что полиномы - это наименьший класс, который позволяет составлять «эффективные алгоритмы»; то есть алгоритм с полиномиальным временем, который вызывает полиномиальное время подпрограмма по-прежнему дает алгоритм с полиномиальным временем.^[11] Если ${ Displaystyle п ^ {2}}$ bound, однако, использовались, то составление постоянного числа «эффективных» алгоритмов может привести к новому алгоритму, который не будет «эффективным». (Обратите внимание, что определение п полезен еще и потому, что эмпирически почти все задачи в п которые практически полезны, на самом деле имеют полиномиальное время выполнения низкого порядка, и почти все проблемы за пределами п которые практически полезны, не имеют известных алгоритмов с малым экспоненциальным временем выполнения, т.е. с ${ Displaystyle О (с ^ {п})}$ время выполнения, где ${ displaystyle c}$ близко к 1.^[12])

Твердость и полнота

Многие классы сложности определены с использованием концепции снижение. Редукция - это превращение одной проблемы в другую. Он отражает неформальное представление о том, что проблема не менее сложна, чем другая проблема. Например, если проблема ${ displaystyle X}$ можно решить с помощью алгоритма для ${ displaystyle Y}$, ${ displaystyle X}$ не сложнее, чем ${ displaystyle Y}$, и мы говорим, что ${ displaystyle X}$ уменьшает к ${ displaystyle Y}$. Существует много различных типов скидок в зависимости от метода сокращения, например Скидки на приготовление еды, Редукции Карпа и Левин редукции, и оценка сложности редукций, например редукции за полиномиальное время или же сокращение пространства журнала.

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

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

Если проблема ${ displaystyle X}$ в C и тяжело для C, тогда ${ displaystyle X}$ как говорят полный за C. Это означает, что ${ displaystyle X}$ самая сложная проблема в C (поскольку может быть много не менее сложных проблем, можно сказать, что ${ displaystyle X}$ так же сложно, как и самые сложные проблемы в C). Таким образом, класс НП-полный проблемы содержат самые сложные проблемы в НП, в том смысле, что они, скорее всего, не будут в P. Потому что проблема п = НП не решена, имея возможность уменьшить известную НП-полная задача, Π₂, к другой проблеме, Π₁, означало бы, что не существует известного решения за полиномиальное время для Π₁. Это связано с тем, что решение Π за полиномиальное время₁ даст решение за полиномиальное время для Π₂. Точно так же, потому что все НП задачи можно свести к набору, найдя НП-полная задача, которую можно решить за полиномиальное время, означает, что п = НП.

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

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

Теорема Савича устанавливает, что PSPACE = NPSPACE и EXPSPACE = NEXPSPACE. Один из центральных вопросов теории сложности заключается в том, добавляет ли недетерминизм значительную мощность вычислительной модели. Это центральное место в открытом п против НП проблема в контексте времени. Теорема Сэвича показывает, что для пространства недетерминизм не добавляет значительно большей мощности, где «значительный» означает разницу между полиномиальными и суперполиномиальными требованиями к ресурсам (или, для EXPSPACE, разность между экспоненциальной и суперэкспоненциальной). Например, теорема Сэвича доказывает, что никакая проблема, требующая экспоненциального пространства для детерминированной машины Тьюринга, не может быть решена с помощью недетерминированной машины Тьюринга с полиномиальным пространством.

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

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

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

${ displaystyle { mathsf {DTIME}} { big (} f (n) { big)} subsetneq { mathsf {DTIME}} { big (} f (n) cdot log ^ {2} (ж (п)) { большой)}}$.

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

${ displaystyle { mathsf {DSPACE}} { big (} f (n) { big)} subsetneq { mathsf {DSPACE}} { big (} f (n) cdot log (f (n )){большой )}}$.

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

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

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

• Ряд классов определяется с помощью вероятностные машины Тьюринга, включая классы BPP, PP, RP, и ЗПП
• Ряд классов определяется с помощью интерактивные системы доказательства, включая классы IP, MA, и ЯВЛЯЮСЬ
• Ряд классов определяется с помощью Булевы схемы, включая классы П / поли и его подклассы NC и AC
• Ряд классов определяется с помощью квантовые машины Тьюринга, включая классы BQP и QMA

Они объясняются более подробно ниже.

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

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

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

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

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

Отношения между фундаментальными классами вероятностной сложности. BQP - вероятностный квантовая сложность class и описан в разделе квантовых вычислений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. (Полнота) строка ${ displaystyle w}$ в ${ displaystyle L}$ подразумевает ${ displaystyle Pr [V { text {принимает}} w { text {после взаимодействия с}} P] geq { tfrac {2} {3}}}$
2. (Прочность) струна ${ displaystyle w}$ не в ${ displaystyle L}$ подразумевает ${ displaystyle Pr [V { text {принимает}} w { text {после взаимодействия с}} P] leq { tfrac {1} {3}}}$

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

Модификация протокола для IP производит еще один важный класс сложности: ЯВЛЯЮСЬ (Протокол Артура – ​​Мерлина). В определении интерактивных систем доказательства, используемых IP, доказывающая сторона не могла видеть монеты, используемые верификатором в его вероятностных вычислениях - она ​​могла видеть только сообщения, которые верификатор генерировал с этими монетами. По этой причине монеты называются частные случайные монеты. Интерактивная система проверки может быть ограничена таким образом, чтобы монеты, используемые проверяющим, были публичные случайные монеты; то есть доказывающий может видеть монеты. Формально, ЯВЛЯЮСЬ определяется как класс языков с интерактивным доказательством, в котором проверяющий отправляет случайную строку доказывающему, проверяющий отвечает сообщением, а проверяющий либо принимает, либо отклоняет, применяя детерминированную функцию полиномиального времени к сообщению из испытатель. ЯВЛЯЮСЬ можно обобщить на ЯВЛЯЮСЬ[k], где k - количество обмененных сообщений (поэтому в обобщенном виде стандарт ЯВЛЯЮСЬ определено выше ЯВЛЯЮСЬ[2]). Однако это так, что для всех k${ displaystyle geq}$2, ЯВЛЯЮСЬ[k] =ЯВЛЯЮСЬ[2]. Также верно, что ЯВЛЯЮСЬ[k]${ displaystyle substeq}$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 клин}$ узлы И ворота, то ${ displaystyle vee}$ узлы ИЛИ ворота, а ${ displaystyle neg}$ узлы НЕ ворота.

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

Формально логическая схема ${ displaystyle C}$ это ориентированный ациклический граф в котором ребра представляют собой провода (которые несут кусочек значения 0 и 1), входные биты представлены исходными вершинами (вершинами без входящих ребер), а все не исходные вершины представляют логические ворота (обычно И, ИЛИ ЖЕ, и НЕ ворота ). Один логический вентиль назначается выходным вентилем и представляет собой конец вычисления. Входное / выходное поведение схемы ${ 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}}$.

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

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

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

Класс сложности П / поли - это множество языков, которые разрешимы с помощью семейств схем полиномиального размера. Оказывается, существует естественная связь между сложностью схемы и временной сложностью. Интуитивно понятно, что язык с небольшой временной сложностью (то есть требует относительно небольшого количества последовательных операций на машине Тьюринга) также имеет небольшую сложность схемы (то есть требует относительно небольшого числа логических операций). Формально можно показать, что если язык на ${ Displaystyle { mathsf {DTIME}} (т (п))}$, куда ${ displaystyle t}$ это функция ${ displaystyle t: mathbb {N} to mathbb {N}}$, то у него схемная сложность ${ Displaystyle О (т ^ {2} (п))}$.^[14] Непосредственно из этого факта следует, что п${ displaystyle substeq}$П / поли. Другими словами, любая проблема, которая может быть решена за полиномиальное время с помощью детерминированной машины Тьюринга, также может быть решена с помощью семейства схем полиномиального размера. Далее, включение правильное, т. Е. п${ displaystyle subset}$П / поли (например, есть некоторые неразрешимые проблемы которые находятся в П / поли).

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

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

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

Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (Апрель 2017 г.)

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

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

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

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

А проблема подсчета спрашивает не только, существует ли решение (как с проблема решения ), но спрашивает Как много решения существуют.^[16] Например, проблема решения ${ displaystyle CYCLE}$ спрашивает ли конкретный график ${ displaystyle G}$ имеет простой цикл (ответ простой да / нет); соответствующая задача подсчета ${ displaystyle #CYCLE}$ (произносится как «резкий цикл») спрашивает Как много простые циклы ${ displaystyle G}$ имеет.^[17] Таким образом, выход для задачи подсчета - это число, в отличие от выходных данных для задачи решения, которая представляет собой простое да / нет (или принять / отклонить, 0/1 или другую эквивалентную схему).^[18] Итак, в то время как проблемы решения математически представлены как формальные языки математически задачи счета представлены в виде функции: задача счета формализуется как функция ${ displaystyle f: {0,1 } ^ {*} to mathbb {N}}$ так что для входа ${ Displaystyle ш в {0,1 } ^ {*}}$, ${ displaystyle f (w)}$ - количество решений. Например, в ${ displaystyle CYCLE}$ проблема, вход - график ${ displaystyle G}$ и ${ Displaystyle f (G)}$ это количество простых циклов в ${ displaystyle G}$.

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

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

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

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

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

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

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

Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (Май 2020 г.)

Задачи подсчета - это подмножество более широкого класса задач, называемых функциональные проблемы. Функциональная проблема - это вычислительная проблема где один выход (из общая функция ) ожидается для каждого входа, но выход более сложный, чем у проблема решения. Для функциональных проблем вывод не просто «да» или «нет». Класс сложности FP - это набор функциональных задач, которые могут быть решены детерминированная машина Тьюринга в полиномиальное время.^[21]

Обещай проблемы

Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (Май 2020 г.)

Резюме отношений между классами сложности

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

		Решение проблемы
Тип 0 (рекурсивно перечисляемый)				Неразрешимый
Разрешимый
EXPSPACE
NEXPTIME
EXPTIME
PSPACE
Тип 1 (контекстно-зависимый)
		со-НП	BQP		НП
			BPP
		п
	NC
Тип 2 (без контекста)
Тип 3 (Обычный)

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

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

Рекомендации

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

• Арора, Санджив; Варак, Вооз (2009). Вычислительная сложность: современный подход. Издательство Кембриджского университета. ISBN  978-0-521-42426-4.
• Сипсер, Майкл (2006). Введение в теорию вычислений (2-е изд.). США: Thomson Course Technology. ISBN  978-0-534-95097-2.

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

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