Дополнение (сложность)
В теории сложности вычислений дополнением ответов к проблеме принятия решения является проблема решения, возникающая в результате изменения местами «да» и «нет» . [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 , который является детерминированным классом.
Каждый класс, который низок сам по себе, замкнут при дополнении.
Ссылки [ править ]
- ^ Ито, Киёси (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), Введение в теорию сложности , Международная серия Прентис Холл по информатике, Прентис Холл, стр. 133–134, ISBN 9780139153808 .
- ^ Воллмер, Гериберт (1999), Введение в сложность схем: единый подход , Тексты по теоретической информатике. Серия EATCS, Springer, стр. 113, ISBN 9783540643104 .
- ^ Прюим, Р.; Вегенер, Инго (2005), Теория сложности: исследование пределов эффективных алгоритмов , Springer, стр. 66, ISBN 9783540274773 .
- ^ Осиелло, Джорджио (1999), Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимации , Springer, p. 189, ISBN 9783540654315 .