NP-твердость
-
Определение NP-сложности
- NP-сложная задача — это задача, для которой существует полиномиальное сокращение от любой задачи в NP.
- Если решение задачи H занимает 1 единицу времени, то решение H может быть использовано для решения любой задачи в NP за полиномиальное время.
-
Невозможность полиномиального решения
- Если P ∈ NP, то NP-сложные задачи не могут быть решены за полиномиальное время.
- Некоторые NP-сложные задачи оптимизации могут быть аппроксимированы до постоянного коэффициента или даже до любого коэффициента.
-
Примеры NP-сложных задач
- Задача коммивояжера и задача о сумме подмножеств являются NP-сложными.
- Проблема остановки и логическая выполнимость являются NP-сложными, но не NP-полными.
- Язык истинных количественных булевых формул является NP-сложным, но не NP-полным.
-
Применение NP-сложных задач
- NP-сложные задачи используются в различных областях, включая планирование, криптографию и интеллектуальный анализ данных.
-
Именование и классификация NP-сложных задач
- NP-сложные задачи не обязательно должны быть элементами класса NP.
- NP-сложные задачи могут быть классифицированы как NP-полные или не NP-полные.
-
Рекомендации
- Ссылки на списки проблем и нерешенных задач, а также на сокращение и непознаваемость в статье.
Полный текст статьи: