Пример. Пусть дана последовательность из нулей и единиц, и нам нужно выяснить, есть ли там хоть одна единица. Алгоритм будет последовательно проверять, нет ли единицы в текущем бите, а затем двигаться дальше, пока вход не кончится. Поскольку единица действительно может быть только одна, для получения точного ответа на этот вопрос в худшем случае придется проверить все n символов входа. В результате получаем сложность порядка cn, где c - количество шагов, потребное для проверки текущего символа и перехода к следующему. Поскольку такого рода константы сильно зависят от конкретной реализации, математического смысла они не имеют, и их обычно прячут за символом O: в данном случае специалист по теории сложности сказал бы, что алгоритм имеет сложность O(n); иными словами, он линейный. Говорят, что алгоритм полиномиальный, если его сложность оценивается сверху некоторым многочленом p(n); алгоритм экспоненциальный, если его сложность имеет порядок 2cn. В реальных, тем более промышленных, задачах редко используются алгоритмы со сложностью больше экспоненты: уже экспоненциальная сложность стала во многих (но не во всех, как мы увидим ниже) случаях синонимом практической неразрешимости и ужасной немасштабируемости. В этой статье мы более никакими теоретико-сложностными концепциями, кроме полиномиального и экспоненциального алгоритма, пользоваться не будем.
Математически есть смысл рассматривать лишь бесконечные последовательности задач: если размер входа ограничен, всякий алгоритм можно заменить большущей, но все же константного размера таблицей, в которой будет записано соответствие между входами и выходами, и алгоритм будет иметь константную сложность (и совершенно не важно, что константа эта может оказаться больше числа атомов во Вселенной).
Мы собирались поговорить о том, насколько теоретические успехи в теории сложности связаны с практикой. В журнальной статье, конечно, невозможно дать обзор всех успехов и неудач теории сложности, так что мы остановимся лишь на трех примерах. Первый из них - биоинформатика - позитивный; в этой области любые теоретические продвижения весьма желательны с практической точки зрения (и продвижения постоянно происходят). Другой пример - линейное программирование - напротив, негативен: здесь один из крупнейших прорывов в теории сложности оказался абсолютно неприменим на практике. Ну а третий пример - решение задачи пропозициональной выполнимости - на мой взгляд, достаточно точно отражает современный баланс между теорией и практикой. Итак, вперед.
