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

 Например, верно ли, что среди чисел {−2, −3, 15, 14, 7, −10, …} есть такие, что их сумма равна 0 (задача о суммах подмножеств)? Ответ да, потому что −2 −3 + 15 −10 = 0 легко проверяется несколькими сложениями (информация, необходимая для проверки положительного ответа, называется сертификатом). Следует ли отсюда, что так же легко подобрать эти числа? Проверить сертификат так же легко, как найти его? Кажется, что подобрать числа сложнее, но это не доказано. 

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

Доказательство в PDF. В нём применяется статистическая физика, что несколько необычно. По всей видимости, автор потратил несколько лет на этот труд.

За доказательство назначен приз в $1,000,000, но об этом ниже. Поясню суть проблемы.

Класс сложности P (или n^O(1)) — это множество алгоритмов, время работы которых не сильно зависит от объёма входных данных. Это быстрые алгоритмы. Точнее: которые могут быть решены на детерминированной машине Тьюринга за полиноминальное время (многочлен от размера данных).

Класс сложности NP — это множество алгоритмов решений, ответ «да» на которые можно проверить за полиноминальное время. NP-полный класс сложности — подмножество NP алгоритмов, для которых неизвестно быстрое решение (за полиноминальное время).

Пример NP-полного алгоритма решения: задача коммивояжёра — проложить оптимальный путь через заданные города, посещая их только один раз. Проверить решение можно быстро (класс P), а найти решение быстро нельзя (класс NP-полный).

Изобразить отношение классов в случае обоих решений теоремы можно на диаграмме Эйлера-Венна:


Доказательство P ≠ NP не только решит одну из семи задач тысячелетия (математический институт Clay, 6 из 7 ещё не решено, решена гипотеза Пуанкаре), но и покажет, что множество криптографических алгоритмов (в частности, на основе проблемы факторизации: публичные и приватные ключи) в безопасности. Также раздел теории вычислений получит полезные инструменты для доказательства других теорем, и не будет биться за поиск P-решений, а сосредоточится на прочих проблемах.

Существует класс coNP — класс P входит и в NP, и в coNP. Если доказано, что NP ≠ coNP, то в coNP не может быть NP-полных проблем.

Приведу некоторые не искусственные проблемы, которые не попадают в класс P и NP-полный:

1. Факторизация целых чисел. Дано целое число, найти простые сомножители.
2. Кратчайший вектор в решётке. Дана решётка L в Rⁿ и целое k, будет ли длина (Евклидова) кратчайшего вектора L находиться в диапазоне [k; kn]?
3. Стохастические игры. Чёрные, Белые и Природа по очереди перемещают фишку по вершинам направленного графа. Природа перемещает случайно. Дан граф, начальная и конечная вершина для фишки. Есть ли у Белых стратегия, которая гарантирует, что фишка достигнет цели с вероятностью ≥ ½?
4. Изоморфизм графа. Даны два графа, являются ли они изоморфными? Другими словами, есть ли взаимо однозначное отображение их вершин, при котором сохранятся рёбра?

Сейчас нет эффективных алгоритмов для этих проблем. Но мы знаем, что первые три находятся и в NP, и в coNP. А значит, если NP ≠ coNP, то они не могут быть NP-полными! А значит, сохраняется вероятность быстрого решения. Аналогичное заключение возможно и для четвёртой проблемы.

Может показаться, что с факторизацией возникло противоречие. Доказательство в данном случае означает, что нет решений класса P, и в то же время проблема не NP-полная.