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

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

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

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

Фон

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Хотя может показаться очевидным различие между классом задач, которые можно эффективно решить, и классом задач, которые можно просто эффективно проверить, на самом деле P и NP находятся в центре одной из самых известных нерешенных проблем в информатике: Проблема P против NP . Хотя известно, что P NP (интуитивно детерминированные машины Тьюринга - это просто подкласс недетерминированных машин Тьюринга, которые не используют свой недетерминизм; или, согласно определению верификатора, P - это класс задач, верификаторы с полиномиальным временем должны только получать пустая строка в качестве сертификата), не известно ли NP строго больше , чем P . Если P = NP , то отсюда следует, что недетерминизм не обеспечивает дополнительных вычислительных мощностей по сравнению с детерминизмом в отношении способности быстро найти решение проблемы; то есть возможность исследовать все возможные ветви вычислений обеспечивает самое большее полиномиальное ускорение по сравнению с возможностью исследовать только одну ветвь. Кроме того, следовало бы , что если доказательство для экземпляра задачи , которые можно быстро проверить правильность существует (то есть, если проблема в NP ), то существует алгоритм , который может быстро построить , что доказательство (то есть, проблема в P ). Однако подавляющее большинство компьютерных ученых считают, что P NP , и большинство используемых сегодня криптографических схем основываются на предположении, что P NP . ${\ displaystyle \ substeq}$${\ 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 \ substeq}$

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

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

L и NL

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

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

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

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

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

PSPACE и NPSPACE

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

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

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

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

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 . Точно так же можно определить логическое закрытие класса и так далее; Однако это делается реже.

Свойства замыкания - одна из ключевых причин, по которой многие классы сложности определены таким образом, как они есть. Возьмем, к примеру, задачу, которую можно решить во времени (то есть за линейное время), и задачу, которая может быть решена в лучшем случае за время. Обе эти проблемы находятся в P , но время выполнения второй растет значительно быстрее, чем время выполнения первой, по мере увеличения размера ввода. Можно спросить, не лучше ли было бы определить класс «эффективно решаемых» проблем, используя некоторую меньшую полиномиальную оценку, например , а не все полиномы, которые допускают такие большие расхождения. Однако оказывается, что полиномы - это наименьший класс функций, содержащий линейные функции, замкнутые относительно сложения, умножения и композиции. Это означает, что полиномы являются наименьшим классом, который позволяет составлять «эффективные алгоритмы»; то есть алгоритм с полиномиальным временем, который вызывает подпрограмму с полиномиальным временем, по- прежнему дает алгоритм с полиномиальным временем. Однако, если бы граница использовалась, то составление постоянного числа «эффективных» алгоритмов могло бы привести к новому алгоритму, который не был бы «эффективным». (Обратите внимание, что определение P также полезно, потому что эмпирически почти все проблемы в P , которые практически полезны, на самом деле имеют полиномиальное время выполнения низкого порядка, и почти все проблемы за пределами P , которые практически полезны, не имеют каких-либо известных алгоритмов с небольшое экспоненциальное время выполнения, то есть со временем выполнения, близким к 1.) ${\ Displaystyle т (п) = п}$${\ Displaystyle т (п) = п ^ {1000}}$${\ Displaystyle п ^ {2}}$${\ Displaystyle п ^ {2}}$${\ Displaystyle О (с ^ {п})}$${\ 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 - Полная проблема, ₂ , для другой проблемы, Π ₁ , будет означать, что не существует известного решения за полиномиальное время для Π ₁ . Это потому, что решение ₁ за полиномиальное время даст решение ₂ за полиномиальное время . Точно так же, поскольку все проблемы NP могут быть сведены к набору, нахождение NP- полной задачи, которая может быть решена за полиномиальное время, будет означать, что P  =  NP . ${\ displaystyle X}$${\ displaystyle X}$${\ displaystyle X}$${\ displaystyle X}$

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

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

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

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

По определению DTIME следует, что он содержится в if , поскольку if . Однако это определение не указывает на то, является ли это включение строгим. Для требований по времени и пространству условия, при которых включение является строгим, задаются теоремами о временной и пространственной иерархии соответственно. Они называются теоремами иерархии, потому что они индуцируют правильную иерархию классов, определенных путем ограничения соответствующих ресурсов. Теоремы об иерархии позволяют делать количественные утверждения о том, сколько еще требуется дополнительного времени или пространства, чтобы увеличить количество проблем, которые могут быть решены. ${\ displaystyle {\ mathsf {DTIME}} (п ^ {k_ {1}})}$${\ displaystyle {\ mathsf {DTIME}} (п ^ {k_ {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} (f (n)) {\ big)}}$.

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

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

Теоремы о временной и пространственной иерархии составляют основу большинства результатов разделения классов сложности. Например, теорема иерархии времени устанавливает, что 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 {принимает}} 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, если существует вероятностная машина Тьюринга M с полиномиальным временем, такая, что если строка не на языке, то M всегда отклоняет, а если строка находится на языке, то M принимает с вероятностью не менее 1 / 2. Класс co-RP определяется аналогично, за исключением того, что роли меняются местами: ошибка не разрешена для строк на языке, но разрешена для строк не на языке. Взятые вместе, классы RP и co-RP охватывают все проблемы, которые могут быть решены с помощью вероятностных машин Тьюринга с односторонней ошибкой .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Булевы схемы

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

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

Любая конкретная схема имеет фиксированное количество входных вершин, поэтому она может воздействовать только на входы такого размера. Однако языки (формальные представления проблем принятия решений ) содержат строки разной длины, поэтому языки не могут быть полностью охвачены одной схемой (это контрастирует с моделью машины Тьюринга, в которой язык полностью описывается одной машиной Тьюринга, которая может работать с любым размером ввода). Таким образом, язык представлен семейством схем . Семейство схем - это бесконечный список схем , где - схема с входными переменными. Семейство схемы называется решить , язык , если для каждой строки , в языке тогда и только тогда , когда есть длина . Другими словами, строка размера находится на языке, представленном семейством схем, если схема (схема с тем же количеством входных вершин, что и количество символов в ней ) оценивается как 1, когда является ее входом. ${\ displaystyle (C_ {0}, C_ {1}, C_ {2}, ...)}$${\ displaystyle C_ {n}}$${\ displaystyle n}$${\ displaystyle L}$${\ displaystyle w}$${\ displaystyle w}$${\ displaystyle L}$${\ Displaystyle C_ {п} (ш) = 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 - это набор языков, которые разрешимы с помощью семейств схем полиномиального размера. Оказывается, существует естественная связь между сложностью схемы и временной сложностью. Интуитивно понятно, что язык с небольшой временной сложностью (то есть требует относительно небольшого числа последовательных операций на машине Тьюринга) также имеет небольшую сложность схемы (то есть требует относительно небольшого числа логических операций). Формально можно показать, что если язык находится в , где - функция , то он имеет схемную сложность . Непосредственно из этого факта следует, что . Другими словами, любая проблема, которая может быть решена за полиномиальное время с помощью детерминированной машины Тьюринга, также может быть решена семейством схем полиномиального размера. Кроме того, это случай, когда включение является правильным, т. Е. (Например, есть некоторые неразрешимые проблемы, которые находятся в P / poly ). ${\ Displaystyle {\ mathsf {DTIME}} (т (п))}$${\ displaystyle t}$${\ displaystyle t: \ mathbb {N} \ to \ mathbb {N}}$${\ Displaystyle О (т ^ {2} (п))}$${\ displaystyle {\ mathsf {\ color {Blue} P}} \ subset {\ textf {P / poly}}}$${\ Displaystyle {\textf {P}} \ subset {\textf {P / poly}}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

		Решение проблемы
Тип 0 (рекурсивно перечисляемый)				Неразрешимый
Разрешимый
EXPSPACE
СЛЕДУЮЩИЙ ВРЕМЯ
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-полноты. Нью-Йорк: WH Freeman & Co., 1979. Стандартный справочник по задачам NP-Complete - важной категории задач, решения которых, по-видимому, требуют непрактично длительного времени для вычисления.