Проблема равенства классов P и NP в информатике

Проблема равенства классов P и NP — это одна из центральных и наиболее известных нерешённых задач в теоретической информатике и математике. Её суть можно сформулировать так: если положительный ответ на какой-то вопрос можно быстро (за полиномиальное время) проверить, то правда ли, что и сам ответ можно быстро найти (тоже за полиномиальное время)? Иными словами, действительно ли проверка решения задачи требует столь же значительных ресурсов, как и его поиск? Формулировка и суть Класс P — это множество задач, которые можно решить «быстро», то есть существуют алгоритмы, работающие за полиномиальное время. Сюда относятся, например, сортировка данных или проверка связности графа. Класс NP — это задачи, для которых предложенное решение можно быстро проверить (тоже за полиномиальное время). То есть если у нас есть «подсказка» (сертификат) — например, список чисел, дающих в сумме ноль в задаче о подмножестве, — мы можем легко убедиться в его правильности. Классический пример — задача коммивояжёра: проверить, что данный маршрут действительно короче определённого порога, легко, а вот найти самый короткий путь — сложно. Из самих определений сразу следует, что P содержится в NP (все задачи, которые решаются быстро, легко и проверить). Вопрос же заключается в том, строго ли это включение, то есть существуют ли задачи, которые лежат в NP, но не лежат в P (то есть задачи, которые нельзя решить быстро, но их решение легко проверить). История Вероятно, впервые вопрос о вычислительной...