В теории сложности вычислений , то дополнение о проблеме решения является проблемой принятия решения в результате реверсирования да и время не ответов. [1] Эквивалентно, если мы определяем проблемы принятия решений как наборы конечных строк, то дополнение этого набора над некоторой фиксированной областью является его проблемой дополнения. [2]
Например, одна важная проблема заключается в том, является ли число простым . Его дополнение позволяет определить, является ли число составным числом (числом, которое не является простым). Здесь область дополнения - это множество всех целых чисел, превосходящих единицу. [3]
Существует сведение по Тьюрингу от каждой проблемы к проблеме ее дополнения. [4] Операция дополнения - это инволюция , что означает, что она «отменяет сама себя», или дополнение к дополнению - это исходная проблема.
Это можно обобщить до дополнения к классу сложности , называемого дополнительным классом , который представляет собой набор дополнений каждой проблемы в классе. [5] Если класс называется C , его дополнение обычно обозначается как co-C . Обратите внимание, что это не дополнение самого класса сложности как набора проблем, который может содержать гораздо больше проблем.
Класс называется закрытым относительно дополнения, если дополнение любой проблемы в классе все еще находится в классе. [6] Поскольку есть редукции Тьюринга от каждой проблемы к ее дополнению, любой класс, который замкнут относительно редукций Тьюринга, замкнут относительно дополнения. Любой класс, замкнутый относительно дополнения, равен своему классу дополнения. Однако при редукции «многие единицы» многие важные классы, особенно NP , считаются отличными от своих дополнительных классов (хотя это не было доказано). [7]
Закрытие любого класса сложности при тьюринговом является подмножеством этого класса , который закрыт под комплементом. Замыкание под дополнением - наименьший из таких классов. Если класс пересекается со своим дополнением, мы получаем (возможно, пустое) подмножество, которое замкнуто относительно дополнения.
Каждый класс детерминированной сложности ( DSPACE (f (n)), DTIME (f (n)) для всех f (n)) закрыт при дополнении, [8], потому что можно просто добавить последний шаг к алгоритму, который меняет ответ . Это не работает для классов недетерминированной сложности, потому что, если существуют оба пути вычислений, которые принимают, и пути, которые отклоняют, и все пути меняют свой ответ, все равно будут пути, которые принимают, и пути, которые отклоняют - следовательно, машина принимает в оба случая.
Некоторые из наиболее удивительных результатов о сложности, показанных на сегодняшний день, показали, что классы сложности NL и SL на самом деле замкнуты относительно дополнения, тогда как раньше широко считалось, что это не так (см. Теорему Иммермана – Селепсеньи ). Последнее стало менее удивительным теперь, когда мы знаем, что SL равен L , что является детерминированным классом.
Каждый класс, который является низким для себя, закрывается дополнением.
Ссылки [ править ]
- ^ Ито, Kiyosi (1993), энциклопедический словарь математики, том 1 , MIT Press, стр. 269, ISBN 9780262590204.
- ^ Шрайвер, Александр (1998), Теория линейного и целочисленного программирования , Серия Уайли по дискретной математике и оптимизации, John Wiley & Sons, стр. 19, ISBN 9780471982326.
- ^ Гомер, Стивен; Селман, Алан Л. (2011), Теория вычислимости и сложности , Тексты в компьютерных науках, Springer, ISBN 9781461406815.
- ^ Сингх, Ариндама (2009), Элементы теории вычислений , Тексты в компьютерных науках, Springer, Упражнение 9.10, стр. 287, ISBN 9781848824973.
- ^ Бовет, Даниэле; Крещенци, Пьерлуиджи (1994), Введение в теорию сложности , Prentice Hall International Series in Computer Science, Prentice Hall, pp. 133–134, ISBN 9780139153808.
- ^ Воллмер, Хериберт (1999), Введение в сложность схем: унифицированный подход , тексты в теоретической информатике. Серия EATCS, Springer, стр. 113, ISBN 9783540643104.
- ^ Pruim, R .; Вегенер, Инго (2005), Теория сложности: изучение пределов эффективных алгоритмов , Springer, стр. 66, ISBN 9783540274773.
- ^ Ausiello, Giorgio (1999), Сложность и приближение: комбинаторные задачи оптимизации и их свойства аппроксимации , Springer, стр. 189, ISBN 9783540654315.
