Как взаимосвязаны классы сложности P и NP в вычислительной математике?

Класс P является подмножеством класса NP, то есть любая задача из P также принадлежит NP, так как её можно проверить за полиномиальное время (проверка решения может состоять просто в повторном решении задачи). 24

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

Суть вопроса заключается в том, означает ли возможность быстрой проверки решения также возможность его быстрого нахождения. 5 Если P и NP окажутся равными, это будет означать, что существуют быстрые алгоритмы для решения всех задач из NP, что может иметь глубокие последствия для теории вычислений, криптографии и множества других областей науки и техники. 5