Шаблон:NP-полные задачи — Википедия WikiZero

NP-полные задачи
Максимизационная задача укладки (упаковки)	Упаковка в контейнеры двумерная упаковка линейная упаковка упаковка по весу упаковка по стоимости Задача о рюкзаке
Теория графов теория множеств	Задача о вершинном покрытии Задача о клике Задача о независимом множестве (наборе) Задача о покрытии множества Задача Штейнера Задача коммивояжёра Обобщённая задача коммивояжёра
Алгоритмические задачи	Задача выполнимости булевых формул (в конъюнктивной нормальной форме)
Логические игры и головоломки	Обобщённые пятнашки (игра в N²-1) задача поиска кратчайшего решения Задачи, решения которых применяются в Тетрис Задача обобщённого судоку Задача о заполнении латинского квадрата Задача какуро
Классы сложности Исследование операций Оптимизация Комбинаторная оптимизация Прикладная математика Теория алгоритмов Динамическое программирование 21 NP-полная задача Карпа