Что такое NP-полные задачи и почему за них дадут миллион
Существует задача, за решение которой Институт Клэя обещал миллион долларов. Самое странное: она не про физику и не про космос, а про то, можно ли решать примеры так же быстро, как их проверять.
Представь задачу, которую ни один компьютер в мире не может решить быстро — но если кто-то даст тебе ответ, ты проверишь его за секунду. Таких задач сотни тысяч, и они связаны хитрым узлом: реши одну быстро — и рухнут все остальные. За доказательство, что это вообще возможно (или невозможно), обещан миллион долларов. Разбираемся, что это за зверь.
Решить и проверить — это не одно и то же
Начнём с простого наблюдения, которое мало кто замечает. Найти решение задачи и проверить чужое готовое решение — это два совершенно разных по сложности дела.
Возьми судоку. Чтобы заполнить пустую сетку с нуля, тебе придётся попотеть: перебирать варианты, возвращаться назад, стирать неудачные числа. А теперь представь, что кто-то протягивает тебе уже заполненную сетку и говорит: «Проверь, всё ли правильно». Ты пробегаешься глазами по строкам, столбцам и квадратам за минуту. Решать — долго. Проверять — мгновенно.
Именно на этом разрыве между «решить» и «проверить» держится одна из главных загадок информатики. И, как ни странно, именно за неё дают миллион долларов.
Знакомься: P и NP
Учёные разложили все задачи по полочкам — классам сложности. Нам нужны две полки.
- Класс P — задачи, которые компьютер умеет быстро решать. «Быстро» здесь означает, что с ростом размера задачи время растёт умеренно — например, как квадрат или куб числа данных, а не взрывается. Отсортировать список, найти кратчайший путь до дома по карте — это P.
- Класс NP — задачи, у которых готовое решение можно быстро проверить. Решить их, может, и тяжело, но проверь чужой ответ — и убедишься в правильности за разумное время. Судоку — классический житель NP.
Заметь: всё, что мы умеем быстро решать, мы умеем и быстро проверять. Поэтому P целиком сидит внутри NP. Большой вопрос звучит так: а есть ли в NP что-то, чего нет в P? Существуют ли задачи, которые легко проверить, но принципиально тяжело решить? Или мы просто пока не придумали хитрый быстрый способ?
Вопрос «равно ли P классу NP» — это вопрос о том, есть ли вообще разница между творчеством и проверкой. Между тем, чтобы придумать доказательство теоремы, и тем, чтобы прочитать готовое.
NP-полные — короли среди трудных
Теперь самое интересное. Внутри NP живёт особая каста задач — NP-полные. Это самые трудные представители класса, и у них есть почти волшебное свойство.
Любую задачу из NP можно переформулировать в виде NP-полной задачи — быстро и без потерь. Это значит, что все NP-полные задачи связаны невидимыми нитями: они, по сути, одна и та же задача в разных костюмах. Если ты придумаешь по-настоящему быстрый способ решать хотя бы одну из них, ты автоматически научишься быстро решать все задачи в NP разом.
Представь связку из тысяч дверей, запертых одним хитрым механизмом. Ты бьёшься над каждой по отдельности — без толку. Но стоит подобрать ключ к одной-единственной двери, как щёлкают все замки сразу. Вот что такое NP-полнота: один ключ открывает весь дом.
Какие это задачи? Их тысячи, и многие до обидного житейские:
- Задача коммивояжёра — обойти десятки городов по кратчайшему маршруту и вернуться домой.
- Раскладка рюкзака — набрать в рюкзак максимально ценный набор вещей, не превысив вес.
- Раскраска карты — раскрасить регионы так, чтобы соседи были разного цвета, уложившись в нужное число красок.
- Расписание — составить расписание уроков или смен так, чтобы ничего не пересекалось.
Все они выглядят разными, но под капотом — одно и то же чудовище.
Почему компьютеры тут буксуют
Возьмём коммивояжёра. С пятью городами всё легко: перебери маршруты руками. Но число вариантов растёт с каждым новым городом не просто быстро, а чудовищно быстро.
Чтобы почувствовать масштаб: добавляешь один город — и количество возможных маршрутов умножается. Для всего лишь пары десятков городов вариантов становится больше, чем песчинок на большом пляже. Самый мощный суперкомпьютер, тупо перебирая всё подряд, будет считать дольше, чем существует Вселенная.
И вот загвоздка: никто не знает быстрого способа. Не «пока не купили достаточно мощный компьютер», а именно — никто не доказал, что такой способ вообще существует. Но и обратного — что его не может быть — тоже никто не доказал. Это и есть открытая дыра в самом фундаменте информатики.
Где тут миллион
В 2000 году Математический институт Клэя выбрал семь самых важных нерешённых задач математики — «Задачи тысячелетия». За каждую назначили приз в миллион долларов. Проблема «P против NP» — одна из них, и на сегодня она по-прежнему не решена.
Чтобы получить миллион, нужно строго доказать одно из двух:
- P = NP — то есть существует волшебный быстрый алгоритм для NP-полных задач, его просто ещё не нашли. Это перевернуло бы мир: рухнула бы значительная часть современной криптографии (шифрование во многом держится на том, что некоторые задачи трудно решать), зато ускорились бы медицина, логистика и наука.
- P ≠ NP — то есть пропасть между «решить» и «проверить» реальна и непреодолима. Большинство учёных верит именно в этот вариант, но верить и доказать — снова две разные задачи.
Самое забавное и честное во всей истории: даже само различие между догадкой и доказательством — это и есть сердце проблемы P против NP. Учёные чувствуют ответ, но строгого доказательства нет уже больше полувека.
Так что если однажды на уроке ты застрянешь над задачкой, которую легко проверить, но мучительно решать, — знай: ты прикоснулся к одному из главных вопросов на стыке математики и информатики. И за ответ на него до сих пор лежит нетронутый миллион.