[[Класс NP]] содержит задачи, которые [[недетерминированная машина Тьюринга]] в состоянии решитьпроверить за полиномиальное количество шагов от размера входных данных. Следует заметить, что недетерминированная машина Тьюринга является лишь абстрактной моделью, в то время как современные компьютеры соответствуют [[Машина Тьюринга|детерминированной машине Тьюринга]] с ограниченной памятью. Поскольку [[детерминированная машина Тьюринга]] может рассматриваться как специальный случай [[недетерминированная машина Тьюринга|недетерминированной машины Тьюринга]], класс NP включает в себя класс P, а также некоторые проблемы, для решения которых известны лишь алгоритмы, экспоненциально зависящие от размера входа (то есть неэффективные для больших входов). В класс NP входят многие знаменитые проблемы, такие как [[задача коммивояжёра]], [[задача выполнимости булевых формул]], [[факторизация]] и др.
