Проблема P против NP: фундаментальный предел в дискретной оптимизации

В теории сложности вычислений все задачи классифицируются по времени их решения. Класс P (Polynomial time) объединяет задачи, которые компьютеры решают быстро — время их работы растет как полином (например, квадрат или куб) от объема входных данных. К этому классу относятся линейное программирование, поиск кратчайшего пути Дейкстры и максимальный поток Диница. Класс NP (Nondeterministic Polynomial time) охватывает все задачи, для которых предложенное решение можно быстро (за полиномиальное время) проверить на правильность. Если кто-то даст вам готовый маршрут коммивояжера, вы легко сложите длины дорог на калькуляторе и проверите, укладывается ли он в лимит. Вопрос P vs NP гласит: равны ли эти два класса? Существует ли скрытый быстрый алгоритм генерации решений для абсолютно всех задач, которые мы умеем быстро проверять?

В 1971 году Стивен Кук и Леонид Левин (а чуть позже Ричард Карп) обнаружили потрясающее явление — NP-полноту. Они математически доказали, что существует элитная группа самых сложных задач в классе NP. Особенность NP-полных задач заключается в их алгебраическом изоморфизме: если кто-нибудь на планете найдет быстрый (полиномиальный) алгоритм хотя бы для одной из них, этот алгоритм мгновенно решит абсолютно все задачи класса NP! Задача коммивояжера, раскраска графов, задача о рюкзаке, сапер, тетрис и взлом криптографии RSA математически сводятся друг к другу. Они все являются разными масками одного и того же комбинаторного демона.

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

Вся современная индустриальная аналитика — это искусство балансирования на краю пропасти NP. Эвристики, алгоритм имитации отжига, генетические алгоритмы, колонии муравьев и методы аппроксимации (где математика гарантирует нахождение ответа, который хуже идеала не более чем на 5%) родились именно из-за невозможности найти абсолютный идеал. Проблема P vs NP превратила исследование операций из сухой алгебраической дисциплины в творческий инжиниринг. Она доказала, что математическое совершенство недостижимо, но создание сверхэффективных, робастных логистических и производственных сетей для нужд глобальной экономики возможно даже в условиях фундаментальной алгоритмической непознаваемости нашего мира.