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