Мы уже видели, что если хотим добиться чего-то в исследовании вычислительной сложности, то нам следует говорить об асимптотическом поведении: не о том, какие задачи могут быть решены за 10000 шагов, а о том, для каких задач примеры размера n могут быть решены за cn² шагов при n, стремящемся к бесконечности. Мы видели TIME (f(n)) — класс всех задач, решаемых за O (f(n)) шагов, и SPACE (f(n)) — класс всех задач, решаемых с использованием O (f(n)) бит памяти.

Но если мы действительно хотим продвинуться дальше, полезно принять еще более грубую модель, в которой различаются полиномиальное и экспоненциальное время, но не различаются времена O(n²) и O(n³). С такой позиции мы будем рассматривать всякую полиномиальную оценку как «быструю», а всякую экспоненциальную оценку — как «медленную».

Я понимаю, что мне сразу же возразят: что, если проблема решаема за полиномиальное время, но полином получается 50000-ного порядка, то есть с n⁵⁰⁰⁰⁰? Или что, если задача занимает экспоненциальное время, но экспонента имеет вид 1,00000001ⁿ? Мой ответ в высшей степени прагматичен: если подобные случаи будут регулярно возникать в практических задачах, то, скорее всего, мы использовали неверную абстракцию. Но до сих пор не было оснований считать, что мы используем неверный подход. Среди крупных задач, решаемых за полиномиальное время, — а это распознавание, линейное программирование, проверка на простоту и т. п. — большая часть и правда имеет практически реализуемые алгоритмы. А из крупных задач, решение которых, по нашему мнению, требует экспоненциального времени, — доказательство теорем, минимизация схемы и т. п. — большинство на самом деле не имеет практичных алгоритмов. Итак, перед вами эмпирический скелет, на котором держится и наш жир, и наши мускулы.