Оглавление
Совместное использование-полное
-
Определение и свойства co-NP-полных задач
- Задачи в co-NP-полном классе являются самыми сложными в co-NP.
- Задачи в co-NP могут быть сведены к co-NP-полным задачам с полиномиальными затратами.
- Если P отличается от co-NP, то все co-NP-задачи неразрешимы за полиномиальное время.
- Если существует быстрый алгоритм для решения co-NP-полной задачи, то он может быть использован для решения всех задач в co-NP.
-
Примеры co-NP-полных задач
- Тавтология – задача определения истинности логических формул.
- Логическая выполнимость – задача определения, существует ли хотя бы одно истинное назначение переменных.
-
Рекомендации по использованию
- Ссылки на внешние ресурсы, включая “Зоопарк сложностей: coNPC”.
Полный текст статьи: