Класс сложности NP (от англ. nondeterministic polynomial — недетерминированные полиномиальные) в контексте теории сложности вычислений — это класс задач, для которых проверка правильности решения может быть выполнена за полиномиальное время, но само решение может быть найдено только за экспоненциальное время (или хуже). 1

Особенность класса: если решение задачи найдено, его корректность может быть проверена быстро, с использованием доступных ресурсов компьютера. 2

Некоторые примеры задач из класса NP: задача о рюкзаке, задача коммивояжёра, задача выполнимости булевых формул (SAT). 1

Класс NP включает в себя класс P, а также некоторые проблемы, для решения которых известны лишь алгоритмы, экспоненциально зависящие от размера входа (то есть неэффективные для больших входов). 4