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

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

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

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

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

Фон [ править ]

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

Вычислительные проблемы [ править ]

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

Проблемы с решением [ править ]

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

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

Вычислительные модели [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

Границы ресурса [ править ]

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

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

Границы времени [ править ]

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

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

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

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

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

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

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

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

Базовые классы сложности [ править ]

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

Классы временной сложности [ править ]

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

P и NP [ править ]

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

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

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

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

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

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

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

Классы космической сложности [ править ]

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

L и NL [ править ]

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

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

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

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

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

PSPACE и NPSPACE [ править ]

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

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

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

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

EXPSPACE и NEXPSPACE [ править ]

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

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

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

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

Свойства классов сложности [ править ]

Закрытие [ править ]

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

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

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

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

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

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

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

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

Отношения между классами сложности [ править ]

Теорема Савича [ править ]

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

Теоремы об иерархии [ править ]

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

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

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

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

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

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

Другие модели вычислений [ править ]

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

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

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

Рандомизированное вычисление [ править ]

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

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

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

Важные классы сложности [ править ]

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

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

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

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

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

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

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

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

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

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

Важные классы сложности [ править ]

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

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

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

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

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

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

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

Логические схемы [ править ]

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

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

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

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

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

Важные классы сложности [ править ]

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

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

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

Квантовые вычисления [ править ]

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

Другие типы проблем [ править ]

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

Проблемы с подсчетом [ править ]

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

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

Важные классы сложности [ править ]

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

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

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

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

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

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

Обещайте проблемы [ править ]

Резюме отношений между классами сложности [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Библиография [ править ]

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

Дальнейшее чтение [ править ]

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