Чтобы понять суть проблемы P и NP, мы должны сначала усвоить понятия «P» и «NP». P относится к классу задач, которые могут быть эффективно решены компьютером за полиномиальное время. Напротив, NP обозначает класс задач, решения которых можно эффективно проверить с помощью компьютера, но еще предстоит эффективно вычислить. Центральный вопрос, возникающий при сравнении P и NP, заключается в том, равно ли P NP или нет. Проще говоря, могут ли проблемы с эффективно проверяемыми решениями быть также и эффективно решаемыми?
Решение проблемы P и NP имеет огромное значение. Если P = NP, это будет означать, что любая проблема, решение которой можно быстро проверить, также может быть решена эффективно. Это открытие произведет революцию в различных областях, от криптографии до оптимизации, и позволит нам решать сложные проблемы гораздо быстрее, чем можно себе представить в настоящее время. С другой стороны, если P ≠ NP, это будет означать, что существуют проблемы, решения которых по своей сути трудно вычислить, даже если их легко проверить. Это подтверждение укрепило бы границы вычислительной осуществимости, защитив безопасность протоколов шифрования и позволив нам оценить присущую сложность некоторых задач.
Несмотря на значительные усилия экспертов на протяжении многих лет, решение проблемы P и NP остается неуловимым. Математический институт Клея даже включил P против NP в число семи «задач тысячелетия», решение которых стоит миллион долларов.