Дополнение (сложность) - Complement (complexity)

В теория сложности вычислений, то дополнять из проблема решения проблема решения, возникающая в результате обращения вспять да и нет ответы.[1] Точно так же, если мы определяем проблемы принятия решений как наборы конечных строк, то дополнять этого множества над некоторой фиксированной областью является проблемой его дополнения.[2]

Например, одна важная проблема заключается в том, является ли число простое число. Его дополнение состоит в том, чтобы определить, является ли число составное число (число, которое не является простым). Здесь область дополнения - это множество всех целых чисел, превосходящих единицу.[3]

Существует Редукция Тьюринга от каждой проблемы до ее дополнения.[4] Операция дополнения - это инволюция, что означает, что он «отменяет сам себя», или дополнение к дополнению является исходной проблемой.

Можно обобщить это до дополнения к класс сложности, называется дополнительный класс, который представляет собой набор дополнений к каждой задаче в классе.[5] Если класс называется C, его дополнение условно обозначается co-C. Обратите внимание, что это нет дополнение самого класса сложности как набора задач, который содержал бы намного больше проблем.

Класс называется закрыт при дополнении если дополнение какой-либо проблемы в классе все еще находится в классе.[6] Поскольку есть редукции Тьюринга от каждой проблемы к ее дополнению, любой класс, который замкнут относительно редукций Тьюринга, замкнут относительно дополнения. Любой класс, замкнутый относительно дополнения, равен своему классу дополнения. Однако под много-одно сокращение, многие важные классы, особенно НП, считаются отличными от своих дополнительных классов (хотя это не было доказано).[7]

В закрытие любого класса сложности при редукциях Тьюринга является надмножеством этого класса, замкнутого относительно дополнения. Замыкание под дополнением - наименьший из таких классов. Если класс пересекается со своим дополнением, мы получаем (возможно, пустое) подмножество, которое замкнуто относительно дополнения.

Каждый класс детерминированной сложности (DSPACE(f (n)), DTIME(f (n)) для всех f (n)) замкнуто относительно дополнения,[8] потому что можно просто добавить последний шаг к алгоритму, который меняет ответ. Это не работает для классов недетерминированной сложности, потому что если существуют оба пути вычисления, которые принимают, и пути, которые отклоняют, и все пути меняют свой ответ, все равно будут пути, которые принимают, и пути, которые отклоняют - следовательно, машина принимает в оба случая.

Некоторые из самых удивительных результатов, показанных на сегодняшний день, показали, что классы сложности NL и SL на самом деле закрыты из-за дополнения, тогда как раньше широко считалось, что это не так (см. Теорема Иммермана – Селепсеньи ). Последнее стало менее удивительным теперь, когда мы знаем SL равно L, который является детерминированным классом.

Каждый класс, который низкий для себя закрыт под комплемент.

Рекомендации

  1. ^ Ито, Киёси (1993), Математический энциклопедический словарь, том 1, MIT Press, стр. 269, ISBN  9780262590204.
  2. ^ Шрайвер, Александр (1998), Теория линейного и целочисленного программирования, Серия Wiley по дискретной математике и оптимизации, John Wiley & Sons, стр. 19, ISBN  9780471982326.
  3. ^ Гомер, Стивен; Селман, Алан Л. (2011), Теория вычислимости и сложности, Тексты по информатике, Springer, ISBN  9781461406815.
  4. ^ Сингх, Ариндама (2009), Элементы теории вычислений, Тексты по информатике, Springer, Exercise 9.10, p. 287, г. ISBN  9781848824973.
  5. ^ Бове, Даниэле; Крещенци, Пьерлуиджи (1994), Введение в теорию сложности, Prentice Hall International Series in Computer Science, Prentice Hall, pp. 133–134, ISBN  9780139153808.
  6. ^ Фоллмер, Хериберт (1999), Введение в сложность схем: единый подход, Тексты по теоретической информатике. Серия EATCS, Springer, стр. 113, ISBN  9783540643104.
  7. ^ Pruim, R .; Вегенер, Инго (2005), Теория сложности: изучение границ эффективных алгоритмов, Springer, стр. 66, ISBN  9783540274773.
  8. ^ Аузиелло, Джорджио (1999), Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимируемости, Springer, стр. 189, г. ISBN  9783540654315.