Дополнение в теории вычислительной сложности

Введение

В теории вычислительной сложности, дополнение к задаче принятия решения — это задача принятия решения, полученная путем обращения ответов "да" и "нет". Эквивалентно, если мы определим задачи принятия решения как множества конечных строк, то дополнение этого множества относительно некоторой фиксированной области определения является его задачей-дополнением. Например, одна важная задача — определение, является ли число простым. Ее дополнение — определение, является ли число составным (число, которое не является простым). Здесь область определения дополнения — множество всех целых чисел, больших единицы. Существует редукция Тьюринга от любой задачи к ее задаче-дополнению. Операция дополнения является инволюцией, то есть она "отменяет сама себя", или дополнение дополнения — это исходная задача. Можно обобщить это на дополнение класса сложности, называемое классом-дополнением, которое представляет собой множество дополнений всех задач в классе. Если класс называется C, его дополнение обычно обозначается как co C. Следует отметить, что это не дополнение самого класса сложности как множества задач, которое содержало бы гораздо больше задач. Класс называется замкнутым относительно дополнения, если дополнение любой задачи в классе также принадлежит этому классу. Поскольку существует редукция Тьюринга от любой задачи к ее дополнению, любой класс, замкнутый относительно редукций Тьюринга, замкнут относительно дополнения. Любой класс, замкнутый относительно дополнения, равен своему классу-дополнению. Однако при использовании многих редукций один-ко-одному многие важные классы, особенно NP, предположительно различны своим классам-дополнениям (хотя это не доказано). Замыкание любого класса сложности относительно редукций Тьюринга является надмножеством этого класса, замкнутым относительно дополнения. Замыкание относительно дополнения — наименьший такой класс. Если класс пересекается со своим дополнением, мы получаем (возможно, пустое) подмножество, замкнутое относительно дополнения. Каждый детерминированный класс сложности (DSPACE(f(n)), DTIME(f(n)) для всех f(n)) замкнут относительно дополнения, поскольку можно просто добавить последний шаг к алгоритму, который инвертирует ответ. Это не работает для недетерминированных классов сложности, поскольку если существуют как пути вычисления, которые принимают, так и пути, которые отклоняют, и все пути инвертируют свой ответ, все равно будут пути, которые принимают, и пути, которые отклоняют, — следовательно, машина принимает в обоих случаях. Аналогично, вероятностные классы, такие как BPP, ZPP, BQP или PP, которые определены симметрично относительно своих случаев "да" и "нет", замкнуты относительно дополнения. В отличие от этого, классы, такие как RP и co RP, определяют свои вероятности с односторонней ошибкой и поэтому не являются (в настоящее время известно) замкнутыми относительно дополнения. Некоторые из самых удивительных результатов сложности, полученных на сегодняшний день, показали, что классы сложности NL и SL на самом деле замкнуты относительно дополнения, тогда как ранее широко считалось, что это не так (см. теорему Иммермана — Селепчени). Последнее стало менее удивительным, теперь, когда мы знаем, что SL равен L, который является детерминированным классом. Каждый класс, который является низким для себя, замкнут относительно дополнения.

In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. Equivalently, if we define decision problems as sets of finite strings, then the complement of this set over some fixed domain is its complement problem. For example, one important problem is whether a number is a prime number. Its complement is to determine whether a number is a composite number (a number which is not prime). Here the domain of the complement is the set of all integers exceeding one. There is a Turing reduction from every problem to its complement problem. The complement operation is an involution, meaning it "undoes itself", or the complement of the complement is the original problem. One can generalize this to the complement of a complexity class, called the complement class, which is the set of complements of every problem in the class. If a class is called C, its complement is conventionally labelled co C. Notice that this is not the complement of the complexity class itself as a set of problems, which would contain a great deal more problems. A class is said to be closed under complement if the complement of any problem in the class is still in the class. Because there are Turing reductions from every problem to its complement, any class which is closed under Turing reductions is closed under complement. Any class which is closed under complement is equal to its complement class. However, under many one reductions, many important classes, especially NP, are believed to be distinct from their complement classes (although this has not been proven). The closure of any complexity class under Turing reductions is a superset of that class which is closed under complement. The closure under complement is the smallest such class. If a class is intersected with its complement, we obtain a (possibly empty) subset which is closed under complement. Every deterministic complexity class (DSPACE(f(n)), DTIME(f(n)) for all f(n)) is closed under complement, because one can simply add a last step to the algorithm which reverses the answer. This doesn't work for nondeterministic complexity classes, because if there exist both computation paths which accept and paths which reject, and all the paths reverse their answer, there will still be paths which accept and paths which reject — consequently, the machine accepts in both cases. Similarly, probabilistic classes such as BPP, ZPP, BQP or PP which are defined symmetrically with regards to their yes and no instances are closed under complement. In contrast, classes such as RP and co RP define their probabilities with one sided error, and so are not (currently known to be) closed under complement. Some of the most surprising complexity results shown to date showed that the complexity classes NL and SL are in fact closed under complement, whereas before it was widely believed they were not (see Immerman–Szelepcsényi theorem). The latter has become less surprising now that we know SL equals L, which is a deterministic class. Every class which is low for itself is closed under complement.