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