Сильная NP-полнота
-
Определение сильной NP-полноты
- Сильная NP-полнота является частным случаем NP-полноты, который остается NP-полным при ограничении числовых параметров полиномом.
- Задача называется строго NP-полной, если она остается NP-полной при ограничении параметров полиномом от длины входных данных.
- Сильная NP-сложность означает, что задача имеет полиномиальную редукцию к другой сильно NP-полной задаче.
-
Примеры задач
- Упаковка мусорного ведра является строго NP-полной, а задача о рюкзаке 0-1 — слабо NP-полной.
- Упаковка контейнеров с целыми числами, ограниченными полиномом, остается NP-полной, в то время как задача о рюкзаке может быть решена псевдополиномиально.
-
Теоретические аспекты
- Если P = NP, то любая сильно NP-сложная задача не имеет схемы аппроксимации за полностью полиномиальное время.
- Если P не равно NP, то некоторые задачи могут быть легко решаемы в среднем, но на практике могут встречаться сложные случаи.
-
Связь с кодированием
- Слабая NP-жесткость соответствует кодированию входных агентов в двоичном кодировании, а сильная NP-жесткость — в унарном кодировании.
- Слабое полиномиальное время соответствует кодированию в двоичном кодировании, а псевдополиномиальное время — в унарном кодировании.