Автор эссе прослеживает, как в информатике сложилось формальное представление об эффективности алгоритмов, и объясняет, почему оно способно уводить исследования от практических задач. Отправной точкой становится работа Джека Эдмондса 1965 года о максимальном паросочетании в графе. Полный перебор давал правильный ответ, но число возможных вариантов росло экспоненциально, тогда как предложенный Эдмондсом алгоритм требовал заметно меньше вычислений.
Чтобы описать это различие, Эдмондс предложил связывать время работы с размером входных данных и оценивать его для сколь угодно больших задач. Верхняя граница его алгоритма составляла n⁴ по числу вершин. Позднее полиномиальное время стали считать признаком «хорошего» алгоритма, а экспоненциальное — «плохого». Этот подход лёг в основу теории сложности и поиска задач, для которых полиномиального решения не существует.
При этом сам Эдмондс предупреждал, что жёсткий критерий не должен мешать разработке полезных методов. Он упоминал симплекс-метод, чья практическая ценность не укладывалась в простую классификацию. Автор добавляет и другую проблему: время n¹⁰⁰⁰ формально полиномиально, но такой алгоритм нельзя считать практически эффективным. Асимптотический подход порождает «галактические алгоритмы» — конструкции, константы и масштабы которых делают реализацию бессмысленной.
Свежим примером автор называет заявленный OpenAI субэкспоненциальный алгоритм для задачи выполнимости SAT. Субэкспоненциальная оценка не означает полиномиальное решение и не решает вопрос P против NP. По объяснению автора, пока число переменных меньше 10 в степени 10²⁵, алгоритм обращается к экспоненциальному полному перебору. Для сравнения, оценка числа атомов во Вселенной составляет лишь около 10⁸⁰. Следовательно, для любых мыслимых практических входов поведение процедуры остаётся экспоненциальным, а улучшение проявляется только в недостижимо далёкой асимптотике.
Автор не отрицает математическую корректность таких границ, но ставит под сомнение их связь с эффективностью в исходном смысле. По его мнению, теория сложности иногда исследует красивые свойства собственных формальных моделей вместо вычислений, которые действительно можно выполнить.