Дополнение (сложность) - Complement (complexity)
В теории сложности вычислений , то дополнение о проблеме решения является проблемой принятия решения в результате реверсирования да и время не ответов. Точно так же, если мы определяем проблемы принятия решений как наборы конечных строк, то дополнение этого набора над некоторой фиксированной областью является его проблемой дополнения.
Например, одна важная проблема заключается в том, является ли число простым . Его дополнение позволяет определить, является ли число составным числом (числом, которое не является простым). Здесь область дополнения - это множество всех целых чисел, превосходящих единицу.
Существует сведение по Тьюрингу от каждой проблемы к проблеме ее дополнения. Операция дополнения - это инволюция , то есть она «отменяет сама себя», или дополнение дополнения - это исходная проблема.
Это можно обобщить до дополнения к классу сложности , называемого дополнительным классом , который представляет собой набор дополнений каждой проблемы в классе. Если класс называется C , его дополнение обычно обозначается как co-C . Обратите внимание, что это не дополнение самого класса сложности как набора проблем, который может содержать гораздо больше проблем.
Класс называется закрытым относительно дополнения, если дополнение любой проблемы в классе все еще находится в классе. Поскольку есть редукции Тьюринга от каждой проблемы к ее дополнению, любой класс, который замкнут относительно редукций Тьюринга, замкнут относительно дополнения. Любой класс, замкнутый относительно дополнения, равен своему классу дополнения. Однако при редукции «многие единицы» многие важные классы, особенно NP , считаются отличными от своих дополнительных классов (хотя это не было доказано).
Закрытие любого класса сложности при тьюринговом является подмножеством этого класса , который закрыт под комплементом. Замыкание под дополнением - наименьший из таких классов. Если класс пересекается со своим дополнением, мы получаем (возможно, пустое) подмножество, которое замкнуто относительно дополнения.
Каждый класс детерминированной сложности ( DSPACE (f (n)), DTIME (f (n)) для всех f (n)) закрыт при дополнении, потому что можно просто добавить последний шаг к алгоритму, который меняет ответ. Это не работает для классов недетерминированной сложности, потому что, если существуют оба пути вычислений, которые принимают, и пути, которые отклоняют, и все пути меняют свой ответ, все равно будут пути, которые принимают, и пути, которые отклоняют - следовательно, машина принимает в оба случая.
Некоторые из наиболее удивительных результатов о сложности, показанных на сегодняшний день, показали, что классы сложности NL и SL на самом деле замкнуты относительно дополнения, в то время как раньше широко считалось, что это не так (см. Теорему Иммермана – Селепсеньи ). Последнее стало менее удивительным теперь, когда мы знаем, что SL равен L , что является детерминированным классом.
Каждый класс, который является низким для себя, закрывается дополнением.