Классы P и NP: Самая главная нерешенная проблема информатики
В 2000 году Математический институт Клэя опубликовал список из семи "Задач тысячелетия", предложив за решение каждой из них награду в один миллион долларов. Одной из них является вопрос, который не дает покоя программистам, криптографам и математикам по всему миру: равны ли классы P и NP (P = NP)? Ответ на этот вопрос в дискретной математике может либо навсегда изменить наш мир, либо подтвердить, что наши текущие ограничения непреодолимы.
Чтобы понять масштаб проблемы, нужно строго определить эти два класса асимптотической сложности:
Класс P (Polynomial time) — это множество задач принятия решений, которые можно быстро решить на классическом детерминированном компьютере. "Быстро" в математическом смысле означает полиномиальное время, то есть время работы алгоритма ограничено сверху многочленом от размера входных данных: O(n), O(n^2), O(n^3) и т.д. К классу P относятся задачи сортировки массивов, поиска кратчайшего пути в графе, умножения матриц. Это те задачи, с которыми наши компьютеры справляются играючи.
Класс NP (Nondeterministic Polynomial time) — это множество задач, решение которых можно быстро проверить, если нам предоставили возможный ответ (подсказку, сертификат). Обратите внимание: не "найти ответ быстро", а именно "проверить готовый". Например, задача коммивояжера, задача о ранце или задача факторизации больших чисел. Найти простые множители огромного числа безумно сложно. Но если кто-то даст вам два числа и скажет "я думаю, это они", вы можете за доли секунды перемножить их и проверить правильность ответа.
Очевидно, что класс P вложен в класс NP (если мы можем быстро найти решение, то уж проверить его мы точно сможем быстро). Но главный вопрос: существуют ли задачи в NP, которые не лежат в P? Большинство ученых интуитивно считают, что P ≠ NP (находить решения объективно сложнее, чем их проверять). Но строгого математического доказательства этого до сих пор нет!
Внутри класса NP есть самое трудное ядро — NP-полные задачи (NP-complete). Теорема Кука-Левина доказала существование таких задач на примере проблемы выполнимости булевых формул (SAT). NP-полные задачи удивительны тем, что они связаны друг с другом: если кто-то в мире найдет быстрый (полиномиальный) алгоритм для хотя бы одной NP-полной задачи, это будет означать, что абсолютно все задачи из NP можно решить быстро. Это привело бы к доказательству P=NP.
Последствия такого открытия (P=NP) были бы грандиозными. Вся современная криптография (RSA, блокчейн, защищенные протоколы банков), основанная на предположении о трудности некоторых математических задач, рухнула бы в одночасье. С другой стороны, мы получили бы идеальные алгоритмы для создания лекарств, оптимизации логистики, обучения нейросетей и решения инженерных задач, которые сейчас требуют тысячелетий работы суперкомпьютеров.
