Разница между классами P и NP заключается в характере задач, которые к ним относятся:

• Класс P — это набор задач, решаемых за полиномиальное (от размера входа) время. 3 Примеры таких задач: задача о существовании пути в графе, задача о взаимно простых числах и т.д.. 3
• Класс NP — это класс задач, верифицируемых (проверяемых) за полиномиальное время. 3 Альтернативное определение: класс задач, решаемых за полиномиальное время на недетерминированной машине Тьюринга. 3 Примеры таких задач: задача о выполнимости булевой формулы, задача о вершинном покрытии, задача о клике и т.д.. 3

Таким образом, задачи из класса P решаются за полиномиальное время в худшем случае, а задачи из класса NP проверяются за полиномиальное время в худшем случае. 1