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