Задача NP-полная (NP-complete problem)

Вычислительная задача называется NP-полной (от англ. non-deterministic polynomial — «недетерминированные с полиномиальным временем»), если для неё не существует эффективных алгоритмов решения.

К этому классу относятся много важных практических задач — задача коммивояжёра, задача раскраски графа, задача покрытия и т.д.

Простые вычислительные задачи могут быть решены за полиномиальное время (класс P). Это значит, что количество итераций или время поиска решения, полиномиально зависит от числа наблюдений исходных данных.

Трудоёмкость более сложных задач экспоненциально растёт с увеличением объема данных. Алгоритмы с экспоненциальным временем считаются неэффективными.

В теории алгоритмов NP-полной является задача с ответом «да» или «нет» из класса NP, к которой можно свести любую задачу из этого класса за полиномиальное время (то есть при помощи операций, число которых не превышает некоторого полинома зависимости от размера исходных данных).

Таким образом, NP-полные задачи образуют в некотором смысле подмножество «типовых» задач в классе NP: если для какой-то из них найден «полиномиально быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро».

Знание, относится ли задача к классу NP-полных, достаточно важно в анализе данных, поскольку в аналитических проектах приходится иметь дело с очень большими объемами исходных данных. Поэтому необходимо планировать вычислительные ресурсы и время для решения задач анализа, и если они неприемлемо возрастают, искать альтернативные пути решения (например, выполнять декомпозицию сложной задачи на ряд простых).