NP-трудные задачи в университете обычно подают так: в теории они разрешимы, но на практике всё безнадёжно дорого. Почти «доказано», что хороших алгоритмов для них нет. Этот миф распространён повсюду: то и дело слышишь «нельзя, тут NP-hard». Но на деле всё не так мрачно. Теория не врёт, просто часто не имеет отношения к реальности. Любой алгоритм взорвётся на каких-то входных данных, но на 99,9% входов — или на 100% реально значимых — он может работать быстро.
Вот несколько известных NP-трудных задач: разрешение зависимостей в пакетных менеджерах, проверка типов (не во всех системах), составление расписаний, задача коммивояжёра (Traveling Salesman) и Boolean Satisfiability (SAT). Для зависимостей пакетов и проверки типов худший случай просто не встречается. Установка пакетов и проверка типов бывают медленными, но автор статьи ни разу не видел «галактического» взрыва. Scheduling и Traveling Salesman — это задачи оптимизации. Обычно советуют брать эвристики, но можно не жертвовать оптимальностью: существуют инструменты, которые находят доказуемо оптимальные решения за приемлемое время. Никакой магии, без квантовых компьютеров. Просто люди думают и придумывают лучшие алгоритмы. За последние десятилетия алгоритмический прогресс обогнал рост железа. Статья, на которую ссылается автор, упоминает ускорение в 450 миллиардов раз между 1991 и 2015 годами.
Даже SAT — архетип NP-трудной задачи — регулярно решают в промышленных масштабах. Amazon ежедневно решает миллиард SMT-задач, а SMT — это ещё более сложная версия SAT. Алгоритмы для SAT стали настолько хороши, что SAT сейчас считают лёгкой частью. А если всё-таки упрёшься в худший случай? Не нужно дожидаться тепловой смерти Вселенной. HTTP-запрос тоже иногда не приходит. Добавь таймаут, покажи сообщение об ошибке — и работаешь дальше.