🤔 Как распознать NP-полную задачу?

Задача NP-полная, если:
- она принадлежит классу NP (решение проверяется за полиномиальное время);
- она неизвестна как решаемая за полиномиальное время, но если бы нашлось решение для одной NP-полной задачи — решились бы и остальные;
- она сводится к другим NP-полным задачам.
Примеры: задача коммивояжёра, рюкзака, раскраски графа.

Ставь 👍 если знал ответ, 🔥 если нет
Забирай 📚Базу Знаний