В чем заключается связь между классами сложности P и NP?

Связь между классами сложности P и NP заключается в том, что задачи из класса P входят в класс NP. 2

Класс P включает задачи, которые решаются за полиномиальное время (от размера входа). 5 Примеры таких задач: задача о существовании пути в графе, задача о взаимно простых числах и т. д.. 5

Класс NP состоит из задач, решение которых можно проверить за полиномиальное время с помощью детерминированной машины Тьюринга. 1 Важно отметить, что NP не обязательно подразумевает, что сама проблема может быть решена за полиномиальное время, а только то, что предлагаемое решение можно быстро проверить. 1 Примеры задач из NP: задача о выполнимости булевой формулы, задача о вершинном покрытии, задача о клике и т. д.. 5

Вопрос о равенстве классов P и NP остаётся открытым. 1 Несмотря на десятилетия исследований, никто ещё не смог доказать ни P = NP, ни P ≠ NP. 1