Дополнение (сложность)
-
Основы теории сложности вычислений
- Задача принятия решения может быть дополнена задачей, где ответы меняются на противоположные.
- Дополнение задачи — это набор строк, которые не входят в исходную область.
-
Примеры и свойства
- Пример: определение простоты числа через определение составных чисел.
- Дополнение множества целых чисел, превышающих единицу, является примером дополнения задачи.
- Тьюринговые сокращения позволяют свести каждую задачу к ее дополнению.
- Дополнение класса сложности co-C является набором дополнений для каждой задачи в C.
-
Закрытые классы и их свойства
- Класс называется закрытым по дополнению, если его дополнение все еще находится в нем.
- Замкнутость по дополнению следует из замкнутости по Тьюрингу.
- Замкнутый класс равен своему дополнению, если он замкнут по дополнению.
-
Различия между детерминированными и недетерминированными классами
- Детерминированные классы сложности, такие как DSPACE(f(n)) и DTIME(f(n)), закрываются дополнением.
- Недетерминированные классы, такие как NP, не закрываются дополнением, так как могут быть пути, которые принимают и отклоняют.
-
Примеры закрытых классов
- Некоторые вероятностные классы, такие как BPP и ZPP, закрываются дополнением.
- Классы RP и co-RP не закрываются дополнением, так как они определяют вероятности с односторонней ошибкой.
-
Новые результаты и их последствия
- Теорема Иммермана-Шелепчени показала, что классы NL и SL замкнуты по дополнению.
- Класс SL теперь известен как детерминированный класс L.
- Каждый низкий класс сложности закрывается дополнением.
Полный текст статьи: