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

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

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

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