Введение

Набор задач в теории вычислительной сложности

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

Предыстория

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

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

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

Проблемы принятия решений

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

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

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

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

Машина Тьюринга — это математическая модель универсальной вычислительной машины. Это наиболее часто используемая модель в теории сложности, что во многом обусловлено тем, что считается, что она столь же мощна, как и любая другая модель вычислений, и её легко анализировать математически. Важно отметить, что предполагается, что если существует алгоритм, решающий определенную задачу, то существует и машина Тьюринга, решающая ту же задачу (это известно как тезис Черча — Тьюринга); это означает, что считается, что любой алгоритм может быть представлен в виде машины Тьюринга. Механически машина Тьюринга (МТ) манипулирует символами (обычно ограничивается битами 0 и 1 для интуитивной связи с реальными компьютерами), содержащимися на бесконечно длинной ленте. МТ может читать и записывать символы по одному, используя ленточную головку. Работа полностью определяется конечным набором элементарных инструкций, например: "в состоянии 42, если видимый символ равен 0, записать 1; если видимый символ равен 1, перейти в состояние 17; в состоянии 17, если видимый символ равен 0, записать 1 и перейти в состояние 6". Машина Тьюринга начинает работу только с входной строкой на ленте, а остальное пространство заполнено пустыми символами. МТ принимает входные данные, если переходит в назначенное состояние принятия, и отклоняет их, если переходит в состояние отклонения. Детерминированная машина Тьюринга (ДМТ) — это самый базовый тип машины Тьюринга. Она использует фиксированный набор правил для определения своих будущих действий (поэтому она называется "детерминированной"). Вычислительная задача может быть определена с точки зрения машины Тьюринга как множество входных строк, которые принимает конкретная машина Тьюринга. Например, задача о простоте, рассмотренная выше, — это множество строк (представляющих натуральные числа), которые принимает машина Тьюринга, работающая с алгоритмом, правильно проверяющим число на простоту. Говорят, что машина Тьюринга распознает язык (вспомните, что "проблема" и "язык" в теории вычислимости и сложности во многом являются синонимами), если она принимает все входные данные, принадлежащие этому языку, и решает язык, если она дополнительно отклоняет все входные данные, не принадлежащие ему (некоторые входные данные могут привести к бесконечному циклу работы машины Тьюринга, поэтому решаемость накладывает дополнительное ограничение на распознавание: машина Тьюринга должна останавливаться на всех входных данных). Машина Тьюринга, которая "решает" задачу, обычно подразумевает машину, которая решает язык. Машины Тьюринга позволяют интуитивно понять понятия "время" и "пространство". Временная сложность МТ для конкретного входа — это количество элементарных шагов, которые машина Тьюринга выполняет, чтобы достичь состояния принятия или отклонения. Пространственная сложность — это количество ячеек на ленте, используемых для достижения состояния принятия или отклонения.

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

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

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

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

Сроки

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

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

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

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

Классы сложности часто определяются с использованием гранулярных наборов классов сложности, называемых DTIME и NTIME (для временной сложности) и DSPACE и NSPACE (для пространственной сложности). Используя нотацию «большое О», они определяются следующим образом: Класс временной сложности DTIME(f(n)) — это множество всех задач, которые решаются детерминированной машиной Тьюринга за время f(n). Класс временной сложности NTIME(f(n)) — это множество всех задач, которые решаются недетерминированной машиной Тьюринга за время f(n). Класс пространственной сложности DSPACE(f(n)) — это множество всех задач, которые решаются детерминированной машиной Тьюринга, использующей пространство f(n). Класс пространственной сложности NSPACE(f(n)) — это множество всех задач, которые решаются недетерминированной машиной Тьюринга, использующей пространство f(n).

P и NP

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

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

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

Проблема P против NP

Хотя может показаться, что существует очевидная разница между классом задач, эффективно решаемых, и классом задач, решения которых можно эффективно проверить, классы P и NP находятся в центре одной из самых известных нерешенных проблем в информатике: проблема P против NP. Хотя известно, что P ⊆ NP (интуитивно, детерминированные машины Тьюринга – это просто подкласс недетерминированных машин Тьюринга, которые не используют свой недетерминизм; или, согласно определению верификатора, P – это класс задач, для которых полиномиальному верификатору достаточно получить пустую строку в качестве свидетельства), неизвестно, строго ли NP больше P. Если P = NP, то следует, что недетерминированность не дает никаких дополнительных вычислительных преимуществ по сравнению с детерминизмом в плане скорости нахождения решения задачи; то есть, возможность исследовать все возможные ветви вычислений обеспечивает, в лучшем случае, полиномиальное ускорение по сравнению с исследованием только одной ветви. Более того, из этого следовало бы, что если для экземпляра задачи существует доказательство, и это доказательство можно быстро проверить на корректность (то есть, если задача принадлежит классу NP), то существует и алгоритм, который может быстро построить это доказательство (то есть, задача принадлежит классу P). Однако подавляющее большинство специалистов в области информатики полагают, что P ≠ NP, и большинство современных криптографических схем основаны на предположении, что P ≠ NP.

EXPTIME и NEXPTIME

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

L и NL

Хотя можно определить классы логарифмической временной сложности, это чрезвычайно узкие классы, поскольку сублинейное время даже не позволяет машине Тьюринга прочитать весь ввод (потому что ). Однако существует значительное число задач, которые могут быть решены в логарифмическом пространстве. Определения этих классов требуют двухленточной машины Тьюринга, чтобы машина могла хранить весь ввод (можно показать, что с точки зрения вычислимости двухленточная машина Тьюринга эквивалентна одноленточной машине Тьюринга). В модели двухленточной машины Тьюринга одна лента является входной, предназначенной только для чтения. Другая – рабочая лента, допускающая как чтение, так и запись, и именно на ней машина Тьюринга выполняет вычисления. Пространственная сложность машины Тьюринга измеряется количеством ячеек, используемых на рабочей ленте. L (иногда расшифровывается как LOGSPACE) определяется как класс задач, разрешимых в логарифмическом пространстве на детерминированной машине Тьюринга, а NL (иногда расшифровывается как NLOGSPACE) – как класс задач, разрешимых в логарифмическом пространстве на недетерминированной машине Тьюринга. Или, более формально, известно, что однако неизвестно, является ли какое-либо из этих соотношений строгим.

PSPACE и NPSPACE

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

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

EXPSPACE и NEXPSPACE

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

Закрытие

Классы сложности обладают различными свойствами замкнутости. Например, классы решений могут быть замкнуты относительно отрицания, дизъюнкции, конъюнкции или даже всех булевых операций. Более того, они могут быть замкнуты относительно различных схем квантификации. P, например, замкнут относительно всех булевых операций и квантификации по областям полиномиального размера. Свойства замкнутости могут быть полезны для разделения классов — один из возможных способов разделения двух классов сложности — найти некоторое свойство замкнутости, которым обладает один класс, но не другой. Каждый класс X, не замкнутый относительно отрицания, имеет класс дополнений co X, который состоит из дополнений языков, содержащихся в X (т.е. co X = X). co NP, например, является важным классом сложности дополнений и находится в центре нерешенной проблемы о том, равен ли co NP классу NP. Свойства замкнутости — одна из ключевых причин, по которым многие классы сложности определены именно так. Возьмем, к примеру, задачу, которую можно решить за время (то есть за линейное время), и задачу, которую можно решить за время, в лучшем случае. Обе эти задачи находятся в P, однако время выполнения второй задачи растет значительно быстрее, чем время выполнения первой, с увеличением размера входных данных. Можно задаться вопросом, не лучше ли определять класс "эффективно решаемых" задач, используя некоторое меньшее полиномиальное ограничение, например, , а не все полиномы, что допускает такие большие расхождения. Однако оказывается, что множество всех полиномов является наименьшим классом функций, содержащим линейные функции и замкнутым относительно сложения, умножения и композиции (например, , который является полиномом, но ). Поскольку мы хотим, чтобы композиция одного эффективного алгоритма с другим эффективным алгоритмом по-прежнему считалась эффективной, полиномы — это наименьший класс, обеспечивающий композицию "эффективных алгоритмов". (Следует отметить, что определение P также полезно, поскольку, эмпирически, почти все практически полезные задачи в P на самом деле имеют полиномиальное время выполнения низкого порядка, и почти для всех практически полезных задач вне P не существует известных алгоритмов с малым экспоненциальным временем выполнения, то есть с временем выполнения, где близко к 1.)

Сокращения

Многие классы сложности определяются с использованием концепции редукции. Редукция – это преобразование одной задачи в другую, то есть редукция принимает входные данные одной задачи и преобразует их в входные данные другой задачи. Например, обычное сложение в десятичной системе можно свести к сложению в двоичной системе, преобразуя 5 и 7 в их двоичное представление (например, 5+7 становится 101+111). Формально, задача A сводится к задаче B, если существует функция f, такая что для любого x, A(x) истинно тогда и только тогда, когда B(f(x)) истинно.

В общем случае, редукции используются для определения того, что одна задача не проще другой. Поэтому мы обычно заинтересованы в использовании редукции за полиномиальное время, поскольку любая задача, которую можно эффективно свести к другой задаче, не сложнее исходной. Формально, задача A полиномиально сводится к задаче B, если существует функция f, вычислимая за полиномиальное время, такая что для всех x, A(x) истинно тогда и только тогда, когда B(f(x)) истинно.

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

Твердость

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

Полная информация

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

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

Теорема Савича устанавливает связь между детерминированными и недетерминированными пространственными ресурсами. Она показывает, что если недетерминированная машина Тьюринга может решить задачу, используя пространство *s*, то детерминированная машина Тьюринга может решить ту же задачу в пространстве *s²*, то есть в квадрате пространства. Формально, теорема Савича утверждает, что для любого *s*,

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

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

Фундаментальные рандомизированные классы сложности времени: ZPP, RP, co RP, BPP и PP. Самый строгий класс – ZPP (вероятностное полиномиальное время с нулевой ошибкой), класс задач, решаемых в полиномиальное время вероятностной машиной Тьюринга с вероятностью ошибки 0. Интуитивно, это самый строгий класс вероятностных задач, поскольку он не допускает никакой ошибки. Немного более широкий класс – RP (рандомизированное полиномиальное время), который не допускает ошибку для строк, не принадлежащих языку, но допускает ограниченную ошибку для строк, принадлежащих языку. Более формально, язык принадлежит классу RP, если существует вероятностная полиномиальная машина Тьюринга, такая, что если строка не принадлежит языку, то она всегда отклоняет, а если строка принадлежит языку, то она принимает с вероятностью не менее 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. ZPP соотносится с RP и co RP следующим образом: ZPP состоит ровно из тех задач, которые принадлежат как RP, так и co RP. Интуитивно это следует из того факта, что RP и co RP допускают только одностороннюю ошибку: co RP не допускает ошибки для строк, принадлежащих языку, а RP не допускает ошибки для строк, не принадлежащих языку. Следовательно, если задача принадлежит как RP, так и co RP, то не должно быть ошибок для строк как в языке, так и вне языка (то есть никакой ошибки), что является точным определением ZPP. Важные рандомизированные классы сложности пространства включают BPL, RL и RLP.

Интерактивные системы проверки

Ряд классов сложности определяются с использованием интерактивных систем доказательств. Интерактивные доказательства обобщают определение доказательств для класса сложности NP и позволяют получить новые сведения в области криптографии, алгоритмов аппроксимации и формальной верификации. Интерактивные системы доказательств – это абстрактные машины, моделирующие вычисления как обмен сообщениями между двумя участниками: доказывающим и проверяющим. Участники взаимодействуют посредством обмена сообщениями, и входная строка считается принятой системой, если проверяющий, на основании полученных от доказывающего сообщений, принимает решение о принятии входных данных. Доказывающий обладает неограниченной вычислительной мощностью, в то время как проверяющий – ограниченной (в стандартном определении интерактивных систем доказательств вычислительная мощность проверяющего ограничена полиномиальным временем). Однако доказывающий не является доверенным лицом (это предотвращает тривиальное распознавание всех языков системой доказательств, когда вычислительно неограниченный доказывающий определяет, принадлежит ли строка языку, а затем отправляет проверяющему достоверный ответ "ДА" или "НЕТ"), поэтому проверяющий должен проводить "допрос" доказывающего, "задавая" ему последовательные вопросы и принимая решение только в том случае, если он достигает высокой степени уверенности в том, что строка принадлежит языку.

Булевые схемы

Альтернативной моделью вычислений по отношению к машине Тьюринга является булева схема — упрощенная модель цифровых схем, используемых в современных компьютерах. Эта модель не только обеспечивает интуитивную связь между вычислениями в теории и вычислениями на практике, но и является естественной моделью для неравномерных вычислений (вычислений, в которых для разных размеров входных данных в рамках одной и той же задачи используются различные алгоритмы). Формально, булева схема представляет собой ориентированный ациклический граф, в котором ребра обозначают проводники (передающие битовые значения 0 и 1), входные биты представлены исходными вершинами (вершинами без входящих ребер), а все неисходные вершины представляют логические элементы (обычно элементы И, ИЛИ и НЕ). Один логический элемент выделяется как выходной и представляет собой конец вычисления. Входное/выходное поведение схемы с входными переменными задается булевой функцией ; например, при входных битах , выходной бит схемы математически представляется как . Схема вычисляет булеву функцию. Любая конкретная схема имеет фиксированное количество входных вершин, поэтому она может работать только с входными данными такого размера. Однако языки (формальные представления задач принятия решений) содержат строки различной длины, поэтому языки не могут быть полностью описаны одной схемой (это отличается от модели машины Тьюринга, в которой язык полностью описывается одной машиной Тьюринга, способной обрабатывать входные данные любого размера). Таким образом, язык представляется семейством схем. Семейство схем — это бесконечный список схем , где — схема с входными переменными. Семейство схем называется решающим для языка , если для каждой строки , строка принадлежит языку тогда и только тогда, когда , где — длина . Иными словами, строка размера принадлежит языку, представленному семейством схем , если схема (схема с тем же количеством входных вершин, что и количество битов в ) возвращает 1 при подаче на вход . В то время как классы сложности, определяемые с использованием машин Тьюринга, описываются в терминах временной сложности, классы сложности схем определяются в терминах размера схемы — количества вершин в схеме. Размерная сложность семейства схем — это функция , где — размер схемы . Знакомые классы функций естественным образом вытекают из этого; например, семейство схем полиномиального размера — это такое, для которого функция является полиномом.

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

Класс сложности P/poly представляет собой множество языков, разрешимых семействами схем полиномиального размера. Оказывается, существует естественная связь между сложностью схем и временной сложностью. Интуитивно, язык с малой временной сложностью (то есть требующий относительно небольшого числа последовательных операций на машине Тьюринга) также имеет малую сложность схемы (то есть требует относительно небольшого числа булевых операций). Формально, можно показать, что если язык находится в , где – функция, то он имеет сложность схемы . Непосредственно из этого следует, что другими словами, любая задача, разрешимая за полиномиальное время детерминированной машиной Тьюринга, также разрешима семейством схем полиномиального размера. Более того, включение является строгим, то есть (например, существуют некоторые неразрешимые задачи, принадлежащие P/poly). P/poly обладает рядом свойств, делающих его весьма полезным при изучении взаимосвязей между классами сложности. В частности, он полезен при исследовании задач, связанных с P против NP. Например, если существует язык в NP, не принадлежащий P/poly, то P/poly также полезен при исследовании свойств полиномиальной иерархии. Например, если NP ⊆ P/poly, то PH схлопывается. Полное описание взаимосвязей между P/poly и другими классами сложности доступно в разделе "Важность P/poly". P/poly также полезен при общем изучении свойств машин Тьюринга, поскольку класс можно эквивалентно определить как класс языков, распознаваемых машиной Тьюринга за полиномиальное время с полиномиально ограниченной функцией подсказок. Два подкласса P/poly, обладающие интересными свойствами сами по себе, – это NC и AC. Эти классы определяются не только с точки зрения размера схемы, но и с точки зрения её глубины. Глубина схемы – это длина самого длинного направленного пути от входного узла к выходному узлу. Класс NC представляет собой множество языков, разрешимых семействами схем, ограниченных не только полиномиальным размером, но и полилогарифмической глубиной. Класс AC определяется аналогично NC, однако допускается неограниченное количество входов для вентилей (то есть вентили AND и OR могут применяться к более чем двум битам). NC является примечательным классом, поскольку его можно эквивалентно определить как класс языков, для которых существуют эффективные параллельные алгоритмы.

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

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

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

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

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

В задаче подсчёта спрашивается не только о существовании решения (как в задаче принятия решения), но и о количестве решений. Например, задача принятия решения спрашивает, содержит ли данный граф простой цикл (ответ – простое «да» или «нет»), а соответствующая задача подсчёта (произносится "sharp cycle") спрашивает, сколько простых циклов содержит этот граф. Таким образом, результатом задачи подсчёта является число, в отличие от результата задачи принятия решения, который представляет собой простое «да/нет» (или «принять/отклонить», 0/1, или другая эквивалентная схема). Следовательно, если задачи принятия решения математически представляются как формальные языки, то задачи подсчёта – как функции: задача подсчёта формализуется как функция f, такая что для каждого входа x, f(x) является количеством решений. Например, в задаче подсчёта циклов входным параметром является граф (представленный в виде строки битов), а f(x) – это количество простых циклов в этом графе.

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

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

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

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

Проблемы с функцией

Проблемы подсчёта являются подмножеством более широкого класса задач, называемых функциональными задачами. Функциональная задача — это тип задачи, в которой вычисляются значения функции. Формально, функциональная задача определяется как отношение над строками произвольного алфавита:

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

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

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