Если NP-сложность изучалась в университете, вывод обычно звучал так: подобные задачи теоретически решаемы, но на практике это безнадёжно дорого. Считается почти доказанным, что хороших алгоритмов для них не существует.
Именно такое впечатление выносит большинство — судя по разговорам с коллегами и обсуждениям в сети. Фраза «нет, так не сделать, это же NP-сложная задача» встречается регулярно. Миф живуч, но сами по себе такие задачи вовсе не являются неразрешимыми на практике.
Финальную лекцию курса один из профессоров завершил драматично (пересказ близко к тексту):
Итак, вы узнали, что почти все интересные задачи неразрешимы, а из оставшихся почти все — NP-сложные. Для всего проекта информатики это последний гвоздь в крышку гроба.
Формулировка мрачная. Не факт, что все восприняли её именно так, но это многое объясняет.
Теория здесь не ошибается, но на практике часто оказывается нерелевантной. Да, любой придуманный алгоритм рано или поздно взорвётся на каком-нибудь входе. Но быстрое решение может находиться для 99,9% входных данных. Или для 100% реально встречающихся на практике. Теория этого не исключает.
В теории нет разницы между теорией и практикой. На практике — есть.
— Бенджамин Брюстер
Несколько известных NP-сложных задач:
- Разрешение зависимостей (в пакетных менеджерах)
- Проверка типов (не во всех системах типов)
- Планирование расписаний
- Задача коммивояжёра
- Булева выполнимость (SAT)
Для пунктов (1) и (2) худший случай попросту не встречается на практике. Установка пакетов и проверка типов, конечно, может быть медленной. Но за годы работы «галактического» взрыва вычислительной сложности не наблюдалось ни разу.
(3) и (4) технически являются задачами оптимизации. Их принято решать эвристиками, но жертвовать оптимальностью решения вовсе не обязательно. Существуют инструменты, которые способны находить доказуемо оптимальные решения за разумное время. Никакой магии, никаких квантовых компьютеров — просто более качественные алгоритмы, придуманные людьми, которые как следует подумали над проблемой. За последние десятилетия прирост эффективности алгоритмов даже опередил рост производительности железа. По данным одной научной работы, между 1991 и 2015 годами совокупное ускорение составило 450 миллиардов раз.
И наконец, даже (5) — архетипическая NP-сложная задача — рутинно решается в промышленных масштабах. Amazon обрабатывает миллиард SMT-запросов в день. SMT — это ещё более сложная версия SAT. Алгоритмы решения SAT настолько продвинулись, что теперь эта часть задачи считается простой.
А что делать, если всё же попадётся худший случай? Ждать тепловой смерти вселенной не придётся. HTTP-запрос тоже иногда не возвращает ответ вовремя — ставится таймаут, показывается сообщение об ошибке, и всё идёт своим чередом.