Объясните проблему равенства P- и NP-классов?

Проблема равенства P- и NP-классов состоит в следующем: если положительный ответ на какой-то вопрос можно довольно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно довольно быстро найти (также за полиномиальное время и используя полиномиальную память)? ru.ruwiki.ru Другими словами, действительно ли решение задачи проверить не легче, чем его отыскать? ru.ruwiki.ru

Класс P — это те задачи, для которых существует эффективный алгоритм решения, позволяющий решать их за полиномиальное время. habr.com Класс NP — это задачи, для которых можно быстро проверить имеющееся решение, хотя для поиска этого решения может потребоваться полный перебор всех вариантов. dzen.ru

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

Проблема равенства классов P и NP важна настолько, что её называют основной проблемой теории алгоритмов или одной из задач тысячелетия. ru.hexlet.io