NP-трудные задачи давно решают на практике вопреки вузовскому мифу

Блог-пост «NP-overrated» опровергает распространённое со студенческой скамьи убеждение: NP-трудные задачи вроде бы решаемы в теории, но на практике обходятся безнадёжно дорого, а отсутствие для них хороших алгоритмов, почти доказанный факт. Автор пишет, что к такому выводу пришёл сам и что то же самое слышал почти от всех, с кем доводилось это обсуждать, а аргумент «это же NP-трудная задача, тут ничего не сделаешь» до сих пор постоянно всплывает в онлайн-спорах, миф живуч, хотя сами задачи вовсе не так безнадёжны. Заключительные слова профессора на последней лекции курса автор пересказывает, с прямой оговоркой, что перефразирует, а не цитирует дословно: студенты только что узнали, что почти все интересные задачи в принципе неразрешимы, а из оставшихся почти все NP-трудны, и для информатики как проекта это «последний гвоздь в крышку гроба».

Возражение автора: теория не ошибается, но на практике часто нерелевантна. Любой алгоритм действительно «взрывается» на каких-то входных данных, но теория не запрещает получать быстрое решение на 99,9% входов или вовсе на 100% тех, что реально встречаются на практике. Здесь же приведён афоризм, приписываемый Бенджамину Брюстеру: «В теории между теорией и практикой нет разницы. Но на практике она есть».

Дальше, разбор пяти характерных NP-трудных задач. Разрешение зависимостей в пакетных менеджерах и проверка типов (не во всех системах типов) действительно бывают медленными, но, по словам автора, катастрофических «зависаний» за свою карьеру он не встречал. Составление расписаний и задача коммивояжёра формально являются задачами оптимизации: их можно решать эвристиками, но жертвовать оптимальностью не обязательно, существуют инструменты, находящие доказуемо оптимальные решения за разумное время. Никакой магии и квантовых компьютеров, просто более качественные алгоритмы: по словам автора, рост эффективности алгоритмов за последние десятилетия обгонял рост производительности самого железа, и он ссылается на статью, где приведена оценка ускорения алгоритмов в 450 миллиардов раз за 1991, 2015 годы (ни автор, ни название статьи в посте не названы). Наконец, булева выполнимость (SAT), «архетип» NP-трудных задач, и её более сложная версия SMT решаются в промышленных масштабах: по утверждению автора, Amazon обрабатывает миллиард SMT-задач в день, а сами SAT-алгоритмы стали настолько эффективными, что SAT теперь считается «лёгкой частью» (источник этой цифры в тексте дан ссылкой на блог Amazon Science).

Что делать, если наихудший случай всё-таки настанет? Автор отвечает буднично: не нужно ждать тепловой смерти вселенной, как и с зависшим HTTP-запросом, достаточно поставить таймаут и показать сообщение об ошибке.

Ключевые факты

Университетский миф: раз задача NP-трудна, «хороших» алгоритмов для неё практически доказанно не существует, автор пересказывает похожие прощальные слова профессора («последний гвоздь в крышку гроба» для информатики), сразу оговариваясь, что не цитирует дословно.
Теория описывает только наихудший случай: любой алгоритм может «взорваться» на каких-то входных данных, но это не запрещает получать быстрое решение на 99,9% входов, или вовсе на 100% тех, что реально встречаются на практике.
Для разрешения зависимостей пакетных менеджеров и проверки типов автор говорит, что за свою карьеру ни разу не видел катастрофического «зависания», хотя оба процесса бывают медленными.
Для планирования и задачи коммивояжёра существуют инструменты, находящие доказуемо оптимальные решения без потери оптимальности за счёт эвристик; автор ссылается на статью об ускорении алгоритмов в 450 миллиардов раз за 1991, 2015 годы (ни автор, ни название статьи в посте не приведены).
Булева выполнимость (SAT), «архетип» NP-трудных задач, и более сложная SMT решаются в промышленных масштабах: по утверждению автора, Amazon обрабатывает миллиард SMT-задач в день, а SAT-алгоритмы стали настолько хороши, что SAT считается «лёгкой частью» (источник цифры Amazon в тексте дан ссылкой на блог Amazon Science).

Почему это важно

В курсах информатики NP-трудность обычно подают как приговор: раз доказано, что задача NP-трудна, «хороших» алгоритмов для неё не существует, и практического смысла её решать нет. Пост разбирает этот вывод и показывает, что он неверно обобщён: теория говорит только о наихудшем случае, а не о типичных входных данных, с которыми реально сталкивается инженер. Практический вывод меняется: NP-трудность задачи сама по себе не повод отказываться от точного или оптимального решения, повод для этого даёт только реальное поведение задачи на конкретных данных.

Кому это важно

Прежде всего, разработчикам и инженерам, которые в работе сталкиваются с классическими NP-трудными задачами: авторам и пользователям пакетных менеджеров (разрешение зависимостей), разработчикам систем типов, тем, кто строит расписания и логистические алгоритмы, пользователям SAT/SMT-солверов. Не менее важно, преподавателям и студентам курсов по теории сложности: пост прямо адресован тому самому выводу, который выносят со студенческой скамьи. И в целом, любому, кто хоть раз слышал (или произносил) фразу «это же NP-трудная задача, тут ничего не сделать» как окончательный аргумент.

Как это применить

Практический вывод автора, не использовать «NP-трудно» как автоматический стоп-сигнал. Прежде чем считать задачу нерешаемой на практике: проверьте, действительно ли ваши реальные входные данные попадают в наихудший случай (чаще всего, нет); поищите готовые решения, которые уже справляются с этим классом задач в промышленных масштабах (SAT/SMT-солверы, точные алгоритмы планирования и коммивояжёра), прежде чем сразу переходить к эвристикам и терять оптимальность. А для того редкого случая, когда наихудший сценарий всё-таки настал, годится тот же приём, что и для любой ненадёжной операции: таймаут и понятное сообщение об ошибке вместо попытки решить задачу любой ценой.

Можно ли доверять

Материал, личное мнение в блоге, а не рецензируемое исследование, и это стоит учитывать. Часть аргументов автор прямо оговаривает как собственный ограниченный опыт («по крайней мере, за мою карьеру»), а не как статистику. Слова профессора приведены как пересказ, а не дословная цитата, это тоже честно оговорено в самом посте. Из двух самых ярких цифр, ускорение алгоритмов в 450 миллиардов раз за 1991, 2015 годы и миллиард SMT-задач в день у Amazon, обе сопровождаются в тексте ссылкой на источник (450 миллиардов раз, на статью на scispace.com, а миллиард SMT-задач в день, на блог Amazon Science), но не именем автора статьи или методологией. Общее направление мысли, что SAT- и SMT-солверы за последние десятилетия совершили резкий практический скачок, соответствует тому, что широко известно в этой области, но сами конкретные числа из поста проверяемы только по этим ссылкам, а не по тексту поста напрямую.

Риски и подводные камни

Главный риск, прочитать пост как «NP-трудность вообще ничего не значит», хотя сам автор этого не утверждает: наихудший случай реален, просто редко совпадает с реальными входными данными, и для него автор предлагает не отрицание проблемы, а обычную инженерную страховку, таймаут и обработку ошибки. Цифры 99,9% и 100% в тексте прямо обозначены как гипотетическая иллюстрация автора, а не измеренный результат, и цитировать их как статистику не стоит. Инструменты, «находящие доказуемо оптимальные решения за разумное время» для планирования и задачи коммивояжёра (Gurobi, SCIP, Google OR-Tools), в посте названы, но не разобраны по размеру задач, на очень больших или специально подобранных входах даже хороший точный алгоритм может забуксовать, а этой оговорки в посте нет. И хотя два самых заметных числа поста, 450-миллиардное ускорение алгоритмов и миллиард SMT-задач в день у Amazon, снабжены в тексте ссылкой на источник, их стоит воспринимать как утверждение автора, а не как проверенный факт.

«В теории между теорией и практикой нет разницы. Но на практике она есть.»

— Бенджамин Брюстер