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