🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
🤔 Как распознать NP-полную задачу?
Задача NP-полная, если:
- она принадлежит классу NP (решение проверяется за полиномиальное время);
- она неизвестна как решаемая за полиномиальное время, но если бы нашлось решение для одной NP-полной задачи — решились бы и остальные;
- она сводится к другим NP-полным задачам.
Примеры: задача коммивояжёра, рюкзака, раскраски графа.
Ставь 👍 если знал ответ, 🔥 если нет
Забирай 📚 Базу знаний