Давайте вместе на секунду представим, что у нас есть ключ вообще от всех замков в мире, которые когда-либо были созданы или, которые когда-либо будут созданы. Этот ключ может мгновенно проверить правильность любого сложнейшего решения от идеального расписания для всех поездов во всех странах до расшифровки самого секретного сообщения. Без этого ключа, для того чтобы найти эти решение с нуля, вам могут потребоваться столетия даже на самом мощном компьютере.
Именно в этом ключике лежит суть проблемы P =? NP — величайшей нерешённой задачи теоретической информатики. За её решение Институт Клэя назначил премию в $1 000 000. Но дело не в деньгах. Дело в фундаменте нашего цифрового мира. Если эта задача будет решена, последствия будут сопоставимы с научной революцией или даже сильнее.
Давайте разберемся, что скрывается за этими двумя буквами, почему это так важно и почему человечество уже 50 лет бьется над этой загадкой.
Класс P (Polynomial time (полиномиальное время)): это множество всех задач, решение которых можно быстро найти. Быстро здесь означает, что время работы алгоритма растет нестрашно относительно размера входных данных (например, как n, n², n³). Примеры:
Сортировка массива из n чисел;
Алгоритм Дейкстры;
Умножение матриц.
Это задачи, которые наши компьютеры решают эффективно каждый день.
Класс NP (Nondeterministic Polynomial time (недетерминированное полиномиальное время)): это множество задач, решение которых можно быстро проверить, если его вам дали. Но вот найти это решение может быть невероятно сложно. Пример: задача коммивояжёра. Дан список городов и расстояний. Нужно найти самый короткий маршрут, проходящий через каждый город ровно один раз и возвращающийся в исходную точку.
Проверка (NP): если вам дали готовый маршрут, вы легко (за полиномиальное время) сложите все расстояния и проверите его длину.
Решение (NP-полная): чтобы найти самый короткий маршрут среди всех возможных, при большом числе городов (n) придётся перебрать n! вариантов. Для 100 городов это больше, чем атомов во Вселенной. Важнейший нюанс: NP — это НЕ «Non-Polynomial». Это распространённая ошибка. NP означает, что решение можно проверить за полиномиальное время на недетерминированной машине Тьюринга (мысленный эксперимент, который может «угадать» верный путь). На практике — это «проверяемые за разумное время» задачи.
Так как на картинке выше затронуты ещё два интересных класса задач, то нужно и о них немного рассказать.
Но перед этим нужно ввести понятие о полиномиальной сводимости. Скоро станет понятно для чего.
Формально говоря, задача A полиномиально сводится к задаче B (запись: A ≤ₚ B), если существует алгоритм, работающий за полиномиальное время, который преобразует любой вход задачи A в эквивалентный вход задачи B так, что: вход задачи A имеет ответ «ДА» тогда и только тогда, когда полученный вход задачи B имеет ответ «ДА».
Можно представить что вы умеете решать одну сложную задачу (например, собирать пазлы). Вам дали другую задачу (например, составить расписание). Вы думаете: «А нельзя ли эту новую задачу превратить в задачу о пазле, решить её как пазл, а потом результат обратно превратить в расписание?». Если такое «превращение» происходит быстро (за полиномиальное время), и решение пазла гарантированно даёт правильное решение для расписания, то полиномиальная сводимость формализует эту идею «превращения» одной задачи в другую.
Теперь переходим к NP-трудной и NP-полной задачам.
NP-трудная задача — это задача, которая по меньшей мере так же трудна, как и самые трудные задачи в классе NP. Задача H является NP-трудной, если для любой задачи L из класса NP выполняется полиномиальное сведение: L ≤ₚ H.
Один важный момент: NP-трудная задача может быть даже сложнее, чем NP. Она может не лежать в классе NP, то есть её решение может быть даже невозможно проверить за полиномиальное время.
NP-полные задачи — точка пересечения двух предыдущих понятий. Задача C является NP-полной, если она удовлетворяет двум условиям:
C ∈ NP (то есть её решение можно быстро проверить, если дано свидетельство);
C является NP-трудной (то есть для любой задачи L из NP верно L ≤ₚ C).
Так в чём же всё-таки сердце проблемы?
Вот главный вопрос, сформулированный в 1971 году Стивеном Куком:
Равны ли классы P и NP?
Другими словами: верно ли, что любую задачу, решение которой можно быстро проверить, можно и быстро решить?
Если P = NP: это означает, что для каждой сложной задачи (из NP) существует (пока не найденный) эффективный алгоритм её решения. Это станет интеллектуальным Big Bang. Мы сможем оптимально проектировать лекарства, мгновенно строить идеальные логистические схемы, создавать искусственный интеллект с невероятными возможностями. Но также рухнет вся современная криптография (RSA, ECC), основанная на том, что разложить число на множители (NP-задача) легко проверить, но сложно сделать.
Если P ≠ NP: это более «скучный» и вероятный, по мнению большинства учёных, сценарий. Он подтвердит нашу интуицию: поиск решения — принципиально сложнее проверки. Некоторые задачи от природы трудны, и мы должны смириться с приближёнными решениями и эвристиками. Цифровой мир останется безопасным (в основе), но мы никогда не получим волшебного ключа от всех замков.
Но почему же это так сложно доказать? Почему имея все современные технологии никто до сих пор не смог этого сделать? Потому что нужно доказать утверждение для всех возможных алгоритмов, которые ещё не придуманы. Мы не можем перебрать их все. Нужна глубокая, фундаментальная теория, которая пока ускользает от нас.
Интересный факт. Внутри класса NP есть уже известная нам элитная группа — NP-полные задачи. Так вот, они обладают удивительным свойством, доказанным Куком и Левиным:
Если для хотя бы одной NP-полной задачи будет найден быстрый (полиномиальный) алгоритм, то ВСЕ задачи из NP станут легкими (перейдут в P). И наоборот, если для одной из них будет доказано, что быстрого алгоритма не существует, то P ≠ NP.
Это даёт учёным мощный инструмент. Чтобы доказать «сложность» новой задачи, достаточно свести к ней одну из известных NP-полных задач (например, задачу выполнимости булевых формул (SAT) или задачу коммивояжёра).
Ещё мне бы хотелось рассказать о некоторых мифах, связанных с теорией, что P = NP.
Миф: «P=NP значит, компьютеры смогут решать всё». Нет, это не так. Есть задачи и сложнее NP (например, EXPSPACE), для которых время решения растёт экспоненциально от размера памяти.
Миф: «Квантовые компьютеры решат проблему». Алгоритм Шора действительно решает задачу факторизации за полиномиальное время на квантовом компьютере, но это не доказывает P=NP. Пока квантовые компьютеры дают ускорение лишь для специфического класса задач (BQP), и большинство экспертов считает, что BQP ≠ NP.
Миф: «Искусственный интеллект уже решил это». Современный ИИ (нейросети) — это мощные эвристики. Они находят удивительно хорошие приближённые решения для NP-трудных задач, но не дают ни точного решения, ни доказательства его оптимальности за полиномиальное время.
Теперь предлагаю немного пофантазировать над тем, каким был бы наш мир, если бы удалось доказать P = NP (и удалось найти конструктивный алгоритм).
Представьте, что в пятницу вечером на GitHub появляется репозиторий universal_np_solver. К утру понедельника мир уже другой.
Конец асимметричного шифрования. Вся криптография, основанная на сложности разложения на множители (RSA) или дискретного логарифма (ECC, DSA), становится историей. Алгоритм берет ваш открытый ключ (произведение двух простых чисел) и за несколько часов выдает приватный. SSL/TLS, PGP, подписи документов всё это превращается лишь в иллюзию безопасности.
Блокчейн и криптовалюты — не устоят. Майнинг (поиск хэша) станет предсказуемым, атака 51% будет тривиальна для любого, у кого есть доступ к алгоритму. Но главное — рухнет сама идея цифровой подписи. Если можно вычислить приватный ключ из публичного, то любой сможет подписаться как вы и потратить ваши биткоины.
Что выживет? Только криптография с информационной стойкостью — одноразовые блокноты, квантовая криптография (и то, только на уровне распределения ключей). Миру придется срочно переходить на абсолютно новые принципы, возможно, основанные на физических законах, а не на вычислительной сложности. Наступит хаотичный переходный период, где все цифровые активы и секреты окажутся под угрозой.
Глобальные цепочки поставок перестанут страдать от кризисов. Алгоритм будет в реальном времени переоптимизировать маршруты тысяч судов, самолетов и грузовиков, учитывая погоду, поломки, спрос и геополитику, минимизируя затраты и выбросы CO2.
Транспорт без пробок станет реальностью не за счет беспилотных машин, а за счет единого оптимального потока. Задача «распределить миллион автомобилей по дорогам мегаполиса за час так, чтобы минимизировать среднее время в пути» будет решена для всего города целиком. Светофор��, полосы, ограничения — всё будет динамически адаптироваться.
Энергетика. Идеальное распределение нагрузки в сетях, оптимальное размещение солнечных панелей и ветряков, прогноз и балансировка потребления — всё это задачи комбинаторной оптимизации. Мы сможем проектировать и управлять энергосистемами с почти 100% КПД.
И это далеко не всё...
P=NP стирает границу между «можно придумать» и «можно найти». Мир станет невообразимо эффективным, болезни отступят, искусство расцветет новыми формами. Но одновременно он станет хрупким (построенным на одном алгоритме), прозрачным (без тайн) и потенциально тоталитарным (потому что кто-то будет задавать вопросы алгоритму).
Вопрос в том, готово ли будет человечество к такому могуществу и сможет ли оно задать алгоритму самый главный, не формализуемый в NP-задачу вопрос: «Что есть благо?».
Это был бы мир, где вычислительная сложность перестает быть ограничением, и на первое место выходит сложность человеческих ценностей и этики. А с ними алгоритм P=NP помочь уже не может.
Возможно это и к лучшему, что вопрос P=? NP так и остаётся открытым.
Надеюсь эта статья была интересной для вас. Спасибо за внимание!
Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩
